Structural parameterizations for boxicity
From MaRDI portal
Publication:289935
DOI10.1007/s00453-015-0011-0zbMath1339.68200arXiv1402.4992OpenAlexW1548626548MaRDI QIDQ289935
Felix Joos, Henning Bruhn, Morgan Chopin, Oliver Schaudt
Publication date: 31 May 2016
Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.4992
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Sublinear approximation algorithms for boxicity and related problems, Approximate association via dissociation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
- Interval representations of planar graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Efficient graph representations
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Boxicity and treewidth
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
- Parameterized Algorithms for Boxicity
- On a Coloring Problem.
- Representation of a finite graph by a set of intervals on the real line
- The Complexity of the Partial Order Dimension Problem
- Polynomial Time and Parameterized Approximation Algorithms for Boxicity
- Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Boxicity and Poset Dimension
