Triangulating Three-Colored Graphs in Linear Time and Linear Space

DOI10.1137/0406023zbMath0798.68127OpenAlexW2051772490MaRDI QIDQ4695390

Alejandro A. Schäffer, Ramana M. Idury

Publication date: 31 October 1994

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

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

zbMATH Keywords

planar graphschordal graphs\(k\)-treesperfect phylogeny problem

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Intervalizing k-colored graphs ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Completing colored graphs to meet a target property ⋮ On intervalizing \(k\)-colored graphs for DNA physical mapping ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs

This page was built for publication: Triangulating Three-Colored Graphs in Linear Time and Linear Space