A 3-approximation for the pathwidth of Halin graphs

DOI10.1016/J.ENDM.2004.03.031zbMATH Open1152.05375OpenAlexW2031516219WikidataQ60488769 ScholiaQ60488769MaRDI QIDQ5899362FDOQ5899362

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

• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• The complexity of searching a graph
• 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
• Title not available (Why is that?)
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Approximation of pathwidth of outerplanar graphs
• Title not available (Why is that?)

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)