A simple linear time algorithm for triangulating three-colored graphs

DOI10.1007/3-540-55210-3_201MaRDI QIDQ5096799zbMATH OpenOpenAlexFDO

Authors Ton Kloks, Hans L. Bodlaender

Publication date 18 August 2022

Published in STACS 92 (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/17939

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15)

Recommendations

• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• Triangulating 3-Colored Graphs
• Three-coloring triangle-free planar graphs in linear time

Cites work

• scientific article; zbMATH DE number 432836 (Why is no real title available?)
• scientific article; zbMATH DE number 437536 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 176762 (Why is no real title available?)
• Algorithms finding tree-decompositions of graphs
• Incidence matrices and interval graphs
• Inferring Evolutionary History From DNA Sequences
• On rigid circuit graphs
• Steiner trees, partial 2–trees, and minimum IFI networks

Cited in

(9)

• scientific article; zbMATH DE number 1843872 (Why is no real title available?)
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Triangulating 3-Colored Graphs
• scientific article; zbMATH DE number 437536 (Why is no real title available?)
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
• Triangulating Vertex-Colored Graphs
• On the block number of graphs
• Three-coloring triangle-free planar graphs in linear time

This page was built for publication: A simple linear time algorithm for triangulating three-colored graphs

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