Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
From MaRDI portal
Publication:5363059
DOI10.1137/1.9781611973730.114zbMath1371.05244arXiv1408.2639OpenAlexW1949878150MaRDI QIDQ5363059
Juraj Stacho, Mathew C. Francis, Pavol Hell
Publication date: 5 October 2017
Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1408.2639
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (6)
Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ A linear-time certifying algorithm for recognizing generalized series-parallel graphs
This page was built for publication: Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
