Name
Abstract | ||
|---|---|---|
Kannan and Warnow [Triangulating Three-Colored Graphs, Proc. 2nd SODA, 1991, pp. 337-343 and SIAM J. Discrete Math., 5 (1992), pp. 249-258] describe an algorithm to decide whether a three-colored graph can be triangulated so that all the edges connect vertices of different colors. This problem is motivated by a problem in evolutionary biology. Kannan and Warnow have two implementation strategies for their algorithm: one uses slightly superlinear time, while the other uses linear time but quadratic space. We note that three-colored triangulatable graphs are always planar, and we use this fact to modify Kannan and Warnow's algorithm to obtain an algorithm that uses both linear time and linear space. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1137/0406023 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
three-colored graph,linear time,linear space,planar graphs | Discrete mathematics,Combinatorics,Colored,Vertex (geometry),Linear space,Quadratic equation,Triangulation,Triangulation (social science),Time complexity,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
6 | 2 | 0895-4801 |
Citations | PageRank | References |
9 | 1.37 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ramana M. Idurys | 1 | 204 | 24.03 |
| Alejandro A. Schäffer | 2 | 827 | 136.66 |