Triangulating Vertex-Colored Graphs

DOI10.1137/S0895480192229273zbMath0796.05087OpenAlexW2059681155MaRDI QIDQ4296524

Thomas Wimer, Fred R. McMorris, Tandy J. Warnow

Publication date: 19 June 1994

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480192229273

zbMATH Keywords

algorithmtriangulationdynamic programming\(k\)-treesvertex-colored graphsperfect phylogeny problemevoluation

Mathematics Subject Classification ID

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

Related Items (21)

Quasi-median graphs from sets of partitions ⋮ Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Trees, taxonomy, and strongly compatible multi-state characters ⋮ On the Generalised Character Compatibility Problem for Non-branching Character Trees ⋮ Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ Enumerating Minimal Tropical Connected Sets ⋮ Recovering trees from well-separated multi-state characters. ⋮ Unique Perfect Phylogeny Is NP-Hard ⋮ Intervalizing k-colored graphs ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ On minimal vertex separators of dually chordal graphs: properties and characterizations ⋮ Tree reconstruction from multi-state characters ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Completing colored graphs to meet a target property ⋮ On intervalizing \(k\)-colored graphs for DNA physical mapping ⋮ Minimizing phylogenetic number to find good evolutionary trees ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Tractability and hardness of flood-filling games on trees ⋮ Exact algorithms for intervalizing coloured graphs

This page was built for publication: Triangulating Vertex-Colored Graphs