A 3-approximation for the pathwidth of Halin graphs

DOI10.1016/J.ENDM.2004.03.031MaRDI QIDQ5899362zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Dimitrios M. Thilikos

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

• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 475622 (Why is no real title available?)
• Algorithms and obstructions for linear-width and related search parameters
• Approximation of pathwidth of outerplanar graphs
• 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
• Graph minors. I. Excluding a forest
• The complexity of searching a graph
• The vertex separation and search number of a graph
• Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen

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 Q5899362)