Fast approximation schemes for K3,3-minor-free or K 5-minor-free graphs

Mohammadtaghi Hajiaghayi; Naomi Nishimura; Prabhakar Ragde; Dimitrios M. Thilikos

doi:10.1016/S1571-0653(04)00379-8

Fast approximation schemes for K_3,3-minor-free or K ₅-minor-free graphs

Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

Computer Science

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

Abstract

We prove that any graph excluding one of K₅ or K_3,3 as a minor has local treewidth bounded by 3k + 4. As a result, we can design practical polynomial-time approximation schemes for both minimization and maximization problems on these classes of non-planar graphs.

Original language	English (US)
Pages (from-to)	137-142
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	10
DOIs	https://doi.org/10.1016/S1571-0653(04)00379-8
State	Published - 2001

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S1571-0653(04)00379-8

Cite this

@article{0d7f3847493e4da1bdbee3df33cdfb33,

title = "Fast approximation schemes for K3,3-minor-free or K 5-minor-free graphs",

abstract = "We prove that any graph excluding one of K5 or K3,3 as a minor has local treewidth bounded by 3k + 4. As a result, we can design practical polynomial-time approximation schemes for both minimization and maximization problems on these classes of non-planar graphs.",

author = "Mohammadtaghi Hajiaghayi and Naomi Nishimura and Prabhakar Ragde and Thilikos, {Dimitrios M.}",

year = "2001",

doi = "10.1016/S1571-0653(04)00379-8",

language = "English (US)",

volume = "10",

pages = "137--142",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Fast approximation schemes for K3,3-minor-free or K 5-minor-free graphs

AU - Hajiaghayi, Mohammadtaghi

AU - Nishimura, Naomi

AU - Ragde, Prabhakar

AU - Thilikos, Dimitrios M.

PY - 2001

Y1 - 2001

N2 - We prove that any graph excluding one of K5 or K3,3 as a minor has local treewidth bounded by 3k + 4. As a result, we can design practical polynomial-time approximation schemes for both minimization and maximization problems on these classes of non-planar graphs.

AB - We prove that any graph excluding one of K5 or K3,3 as a minor has local treewidth bounded by 3k + 4. As a result, we can design practical polynomial-time approximation schemes for both minimization and maximization problems on these classes of non-planar graphs.

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

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

U2 - 10.1016/S1571-0653(04)00379-8

DO - 10.1016/S1571-0653(04)00379-8

M3 - Article

AN - SCOPUS:34247269177

SN - 1571-0653

VL - 10

SP - 137

EP - 142

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Fast approximation schemes for K_3,3-minor-free or K ₅-minor-free graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this