Pathwidth of Circular-Arc Graphs

DOI10.1007/978-3-540-74839-7_25zbMath1141.68549OpenAlexW1546553618MaRDI QIDQ3508573

Ioan Todinca, Karol Suchan

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (11)

Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Edge Search Number of Cographs in Linear Time ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Approximate search strategies for weighted trees ⋮ Mixed Search Number of Permutation Graphs ⋮ Edge search number of cographs ⋮ How to compute digraph width measures on directed co-graphs ⋮ Exclusive graph searching ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Linear rank-width and linear clique-width of trees ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Cites Work

• Unnamed Item
• Computing the vertex separation of unicyclic graphs
• Graph minors. I. Excluding a forest
• A partial k-arboretum of graphs with bounded treewidth
• The vertex separation and search number of a graph
• Linear-time recognition of circular-arc graphs
• Approximation of pathwidth of outerplanar graphs
• Characterizing Minimal Interval Completions
• The complexity of searching a graph
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• TREEWIDTH OF CIRCLE GRAPHS
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Sur deux propriétés des classes d'ensembles
• A 3-approximation for the pathwidth of Halin graphs

This page was built for publication: Pathwidth of Circular-Arc Graphs