Approximating the pathwidth of outerplanar graphs

DOI10.1016/S0020-0190(98)00139-2MaRDI QIDQ293398zbMATH OpenFDO

Authors Rajeev Govindan, Michael A. Langston, Xudong Yan

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

approximationgraph algorithmspathwidthtree decompositionouterplanar graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2044933
• Approximation of pathwidth of outerplanar graphs
• Computing Pathwidth Faster Than 2 n
• 2-connecting outerplanar graphs without blowing up the pathwidth
• A 3-approximation for the pathwidth of Halin graphs

Cites work

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

Cited in

(11)

• scientific article; zbMATH DE number 2044933 (Why is no real title available?)
• Approximation of pathwidth of outerplanar graphs
• Approximability of the path-distance-width for AT-free graphs
• 2-connecting outerplanar graphs without blowing up the pathwidth
• Shortest beer path queries in outerplanar graphs
• Determining the Smallest k Such That G Is k-Outerplanar
• A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs
• Order-preserving 1-string representations of planar graphs
• Linear-time algorithms for problems on planar graphs with fixed disk dimension
• Computing the vertex separation of unicyclic graphs
• A 3-approximation for the pathwidth of Halin graphs

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

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