Approximating the pathwidth of outerplanar graphs

DOI10.1016/S0020-0190(98)00139-2zbMath1339.05386MaRDI QIDQ293398

Rajeev Govindan, Xudong Yan, Michael A. Langston

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001392?np=y

zbMATH Keywords

approximationtree decompositionouterplanar graphsgraph algorithmspathwidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Linear-time algorithms for problems on planar graphs with fixed disk dimension ⋮ Computing the vertex separation of unicyclic graphs ⋮ Order-Preserving 1-String Representations of Planar Graphs ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ 2-connecting outerplanar graphs without blowing up the pathwidth

Cites Work

• Unnamed Item
• Narrowness, pathwidth, and their application in natural language processing
• The vertex separation number of a graph equals its path-width
• A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs
• The vertex separation and search number of a graph
• Graph minors. II. Algorithmic aspects of tree-width
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

This page was built for publication: Approximating the pathwidth of outerplanar graphs