A 3-approximation for the pathwidth of Halin graphs

DOI10.1016/j.endm.2004.03.031zbMath1152.05375OpenAlexW2031516219WikidataQ60488769 ScholiaQ60488769MaRDI QIDQ5899362

Dimitrios M. Thilikos, Fedor V. Fomin

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2004.03.031

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• 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
• The complexity of searching a graph
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

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