A 3-approximation for the pathwidth of Halin graphs

DOI10.1016/j.jda.2005.06.004zbMath1109.05099OpenAlexW2120883068WikidataQ60488758 ScholiaQ60488758MaRDI QIDQ5898649

Dimitrios M. Thilikos, Fedor V. Fomin

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 theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

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

Cites Work

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