×

zbMATH — the first resource for mathematics

Triangulating vertex-colored graphs. (English) Zbl 0796.05087
This paper examines the class of vertex-colored graphs that can be triangulated without the introduction of edges between vertices of the same color. This is related to the perfect phylogeny problem. An algorithm based on dynamic programming is proposed to solve the problem.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
05C15 Coloring of graphs and hypergraphs
68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
92B10 Taxonomy, cladistics, statistics in mathematical biology
PDF BibTeX XML Cite
Full Text: DOI