A 3-approximation for the pathwidth of Halin graphs

Fedor V. Fomin; Dimitrios M. Thilikos

doi:10.1016/j.jda.2005.06.004

A 3-approximation for the pathwidth of Halin graphs

Fedor V. Fomin, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.

Original language	English (US)
Pages (from-to)	499-510
Number of pages	12
Journal	Journal of Discrete Algorithms
Volume	4
Issue number	4
DOIs	https://doi.org/10.1016/j.jda.2005.06.004
State	Published - Dec 2006

Keywords

Halin graph
Linear width
Pathwidth

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jda.2005.06.004

Cite this

@article{ebc03251568643f6b81989297157a394,

title = "A 3-approximation for the pathwidth of Halin graphs",

abstract = "We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.",

keywords = "Halin graph, Linear width, Pathwidth",

author = "Fomin, {Fedor V.} and Thilikos, {Dimitrios M.}",

year = "2006",

month = dec,

doi = "10.1016/j.jda.2005.06.004",

language = "English (US)",

volume = "4",

pages = "499--510",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - A 3-approximation for the pathwidth of Halin graphs

AU - Fomin, Fedor V.

AU - Thilikos, Dimitrios M.

PY - 2006/12

Y1 - 2006/12

N2 - We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.

AB - We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.

KW - Halin graph

KW - Linear width

KW - Pathwidth

UR - http://www.scopus.com/inward/record.url?scp=33750614954&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750614954&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2005.06.004

DO - 10.1016/j.jda.2005.06.004

M3 - Article

AN - SCOPUS:33750614954

SN - 1570-8667

VL - 4

SP - 499

EP - 510

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 4

ER -

A 3-approximation for the pathwidth of Halin graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this