Approximating the pathwidth of outerplanar graphs
From MaRDI portal
Publication:293398
DOI10.1016/S0020-0190(98)00139-2zbMATH Open1339.05386MaRDI QIDQ293398FDOQ293398
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- 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
- 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
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- Title not available (Why is that?)
Cited In (11)
- Order-preserving 1-string representations of planar graphs
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- A 3-approximation for the pathwidth of Halin graphs
- Approximability of the path-distance-width for AT-free graphs
- Title not available (Why is that?)
- 2-connecting outerplanar graphs without blowing up the pathwidth
- Determining the Smallest k Such That G Is k-Outerplanar
- Computing the vertex separation of unicyclic graphs
- A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs
- Approximation of pathwidth of outerplanar graphs
- Shortest beer path queries in outerplanar 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)
