Name
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 $$d \\ge 2$$d¿2. 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-015-0011-0 | Algorithmica |
Keywords | Field | DocType |
Boxicity,Parameterized complexity,kernelization,Treewidth | Integer,Discrete mathematics,Graph,Parameterized complexity,Combinatorics,Vertex (geometry),Computer science,Boxicity,Vertex cover,Pathwidth | Conference |
Volume | Issue | ISSN |
74 | 4 | 0178-4617 |
Citations | PageRank | References |
2 | 0.39 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| henning bruhn | 1 | 177 | 24.93 |
| Morgan Chopin | 2 | 3 | 0.75 |
| Felix Joos | 3 | 37 | 11.20 |
| Oliver Schaudt | 4 | 95 | 21.74 |