Triangulating Vertex-Colored Graphs

DOI10.1137/S0895480192229273MaRDI QIDQ4296524zbMATH OpenOpenAlexFDO

Authors Thomas Wimer, F. 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

\(k\)-treesalgorithmdynamic programmingevoluationperfect phylogeny problemtriangulationvertex-colored graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 437536
• Maximum colorful cycles in vertex-colored graphs
• SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• A simple linear time algorithm for triangulating three-colored graphs

Cited in

(26)

• Trapezoid graphs and their coloring
• Trees, taxonomy, and strongly compatible multi-state characters
• Recovering trees from well-separated multi-state characters.
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Quasi-median graphs from sets of partitions
• On minimal vertex separators of dually chordal graphs: properties and characterizations
• Completing colored graphs to meet a target property
• Bipartite completion of colored graphs avoiding chordless cycles of given lengths
• Some completion problems for graphs without chordless cycles of prescribed lengths
• Tractability and hardness of flood-filling games on trees
• Exact algorithms for intervalizing coloured graphs
• A technique for multicoloring triangle-free hexagonal graphs
• Exact exponential algorithms to find a tropical connected set of minimum size
• Enumerating Minimal Tropical Connected Sets
• Unique perfect phylogeny is NP-hard
• Intervalizing \(k\)-colored graphs
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
• Exact exponential algorithms to find tropical connected sets of minimum size
• On the Generalised Character Compatibility Problem for Non-branching Character Trees
• On intervalizing k-colored graphs for DNA physical mapping
• Minimizing phylogenetic number to find good evolutionary trees
• A Survey on the Complexity of Flood-Filling Games
• Tree reconstruction from multi-state characters
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Vertex-colored encompassing graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4296524)