Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems

Dimitrios M. Thilikos; Hans L. Bodlaender

doi:10.1016/s0020-0190(97)00024-0

Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems

Dimitrios M. Thilikos, Hans L. Bodlaender

Computer Science

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

Abstract

A graph is l-apex if it can be made planar by removing at most l vertices. In this paper we show that the vertex set of any graph not containing an l-apex graph as a minor can be partitioned in linear time into 2^l sets inducing graphs with small treewidth. As a consequence, several maximum induced-subgraph problems when restricted to graph classes not containing some special l-apex graphs as minors, have practical approximation algorithms.

Original language	English (US)
Pages (from-to)	227-232
Number of pages	6
Journal	Information Processing Letters
Volume	61
Issue number	5
DOIs	https://doi.org/10.1016/s0020-0190(97)00024-0
State	Published - Mar 14 1997

Keywords

Algorithms
Analysis of algorithms
Approximation algorithms
Combinatorial problems
Graph minors
Treewidth

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/s0020-0190(97)00024-0

Cite this

@article{83eaaf71aff94a09996dd376dc1e71db,

title = "Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems",

abstract = "A graph is l-apex if it can be made planar by removing at most l vertices. In this paper we show that the vertex set of any graph not containing an l-apex graph as a minor can be partitioned in linear time into 2l sets inducing graphs with small treewidth. As a consequence, several maximum induced-subgraph problems when restricted to graph classes not containing some special l-apex graphs as minors, have practical approximation algorithms.",

keywords = "Algorithms, Analysis of algorithms, Approximation algorithms, Combinatorial problems, Graph minors, Treewidth",

author = "Thilikos, {Dimitrios M.} and Bodlaender, {Hans L.}",

year = "1997",

month = mar,

day = "14",

doi = "10.1016/s0020-0190(97)00024-0",

language = "English (US)",

volume = "61",

pages = "227--232",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems

AU - Thilikos, Dimitrios M.

AU - Bodlaender, Hans L.

PY - 1997/3/14

Y1 - 1997/3/14

N2 - A graph is l-apex if it can be made planar by removing at most l vertices. In this paper we show that the vertex set of any graph not containing an l-apex graph as a minor can be partitioned in linear time into 2l sets inducing graphs with small treewidth. As a consequence, several maximum induced-subgraph problems when restricted to graph classes not containing some special l-apex graphs as minors, have practical approximation algorithms.

AB - A graph is l-apex if it can be made planar by removing at most l vertices. In this paper we show that the vertex set of any graph not containing an l-apex graph as a minor can be partitioned in linear time into 2l sets inducing graphs with small treewidth. As a consequence, several maximum induced-subgraph problems when restricted to graph classes not containing some special l-apex graphs as minors, have practical approximation algorithms.

KW - Algorithms

KW - Analysis of algorithms

KW - Approximation algorithms

KW - Combinatorial problems

KW - Graph minors

KW - Treewidth

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

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

U2 - 10.1016/s0020-0190(97)00024-0

DO - 10.1016/s0020-0190(97)00024-0

M3 - Article

AN - SCOPUS:9644284118

SN - 0020-0190

VL - 61

SP - 227

EP - 232

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this