A 3-approximation for the pathwidth of Halin graphs

DOI10.1016/J.JDA.2005.06.004MaRDI QIDQ5898649zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Dimitrios M. Thilikos

Publication date 14 February 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2005.06.004

zbMATH Keywords

approximation algorithmslinear width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximating the pathwidth of outerplanar graphs
• Computing Pathwidth Faster Than 2 n
• scientific article; zbMATH DE number 4173000
• scientific article; zbMATH DE number 2044933
• Approximation of pathwidth of outerplanar graphs

Cites work

• scientific article; zbMATH DE number 434484 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 475622 (Why is no real title available?)
• scientific article; zbMATH DE number 866659 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Algorithms and obstructions for linear-width and related search parameters
• Approximating the pathwidth of outerplanar graphs
• Approximation of pathwidth of outerplanar graphs
• Computing the vertex separation of unicyclic graphs
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Efficient Planarity Testing
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Graph Classes: A Survey
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Halin graphs and the travelling salesman problem
• Interval graphs and searching
• Lengths of cycles in halin graphs
• Minimum cycle bases of Halin graphs
• Monotonicity in graph searching
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of searching a graph
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width
• Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen

Cited in

(11)

• Fast searching games on graphs
• Pathwidth of Circular-Arc Graphs
• Approximating Pathwidth for Graphs of Small Treewidth
• Treetopes and their graphs
• Approximating the pathwidth of outerplanar graphs
• Approximate search strategies for weighted trees
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Mixed search number and linear-width of interval and split graphs
• Drawing Halin-graphs with small height
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Mixed Search Number and Linear-Width of Interval and Split Graphs

This page was built for publication: A 3-approximation for the pathwidth of Halin graphs

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