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: |
|
||||||||||||||||||||
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: |
|
||||||||||||||||||||
Refereed: | Yes | ||||||||||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/27986 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
View Item |