Search

This is the second paper in a series of two. The goal of the series is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time-algorithm that starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a P6-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This paper considers the problem of determining whether a given set T of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input T is dense, we solve the problem in O(∣T∣) time, which is optimal since the size of the input is ϴ(∣T∣). In comparison, the previously fastest algorithm for this problem runs in O(∣T∣²) time. We also develop an optimal O(∣T∣)-time algorithm for enumerating all simple phylogenetic networks leaf-labeled by L that are consistent with T , where L is the set of leaf labels in T , which is used by our main algorithm. Next, we prove that the problem becomes NP-hard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set T of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883. ∣T∣ of the rooted triplets in T. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5 ⁄12 (> 0.4166) of the rooted triplets in T . [ABSTRACT FROM AUTHOR]

Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an O(∣V∣²) algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an O(∣V∣³) algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs. [ABSTRACT FROM AUTHOR]

In this paper, we present an (n) time worst-case deterministic algorithm for finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple n-sided polygon in the plane. Up to now, only an O(n log n) worst-case deterministic and an O(n) expected time bound have been shown, leaving an O(n) deterministic solution open to conjecture. [ABSTRACT FROM AUTHOR]