Universität zu Köln

Bruhn, Henning, Chopin, Morgan, Joos, Felix and Schaudt, Oliver (2016). Structural Parameterizations for Boxicity. Algorithmica, 74 (4). S. 1453 - 1473. NEW YORK: SPRINGER. ISSN 1432-0541

Full text not available from this repository.

Abstract

The boxicity of a graph G is the least integer d such that G has an intersection model of axis-aligned d-dimensional boxes. Boxicity, the problem of deciding whether a given graph G has boxicity at most d, is NP-complete for every fixed . We show that Boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al. (2010), that Boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that Boxicity admits an additive 1-approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of Adiga et al. (2010) that Boxicity remains NP-complete even on graphs of constant treewidth.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Bruhn, Henning UNSPECIFIED UNSPECIFIED UNSPECIFIED Chopin, Morgan UNSPECIFIED UNSPECIFIED UNSPECIFIED Joos, Felix UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-279867
DOI:	10.1007/s00453-015-0011-0
Journal or Publication Title:	Algorithmica
Volume:	74
Number:	4
Page Range:	S. 1453 - 1473
Date:	2016
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1432-0541
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language GRAPHS Multiple languages Computer Science, Software Engineering; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/27986