Triangulating vertex-colored graphs

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 a fundamental and long-standing problem for numerical taxonomists, called the Perfect Phylogeny Problem. These problems are known t...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 1994-05, Vol.7 (2), p.296-306
Main Authors: MCMORRIS, F. R, WARNOW, T. J, WIMER, T
Format: Article
Language:English
Subjects:
Algorithms
Applied mathematics
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Graphs
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 a fundamental and long-standing problem for numerical taxonomists, called the Perfect Phylogeny Problem. These problems are known to be polynomially equivalent and NP-complete. This paper presents a dynamic programming algorithm that can be used to determine whether a given vertex-colored graph can be so triangulated and that runs in $O( ( n + m ( k - 2 ) )^{k + 1} )$ time, where the graph has $n$ vertices, $m$ edges, and $k$ colors. The corresponding algorithm for the Perfect Phylogeny Problem runs in $O( r^{k + 1} k^{k + 1} + sk^2 )$ time, where $s$ species are defined by $k$$r$-state characters.
ISSN:0895-4801
1095-7146
DOI:10.1137/S0895480192229273