scientific article; zbMATH DE number 7053376

zbMath1421.68126MaRDI QIDQ5743499

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095240

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

treewidthfixed-parameter tractabilityexponential time hypothesissubexponential algorithmbidimensionalityEPTASexcluded grid theoremunit-disc graphmap graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Tree densities in sparse graph classes ⋮ Map graphs having witnesses of large girth ⋮ Linear-time recognition of map graphs with outerplanar witness ⋮ Unnamed Item ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ On embeddability of unit disk graphs onto straight lines ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ Faster algorithms for cycle hitting problems on disk graphs ⋮ Graph product structure for non-minor-closed classes ⋮ Recognizing map graphs of bounded treewidth ⋮ Unnamed Item ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Unnamed Item ⋮ Optimality program in segment and string graphs ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Notes on graph product structure theory ⋮ Decomposition of Map Graphs with Applications. ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum clique partition in unit disk graphs
• Linearity of grid minors in treewidth with applications through bidimensionality
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Unit disk graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• A partial k-arboretum of graphs with bounded treewidth
• Label placement by maximum independent set in rectangles
• Graph searching and a min-max theorem for tree-width
• Quickly excluding a planar graph
• Some APX-completeness results for cubic graphs
• Three-dimensional orthogonal graph drawing algorithms
• Which problems have strongly exponential complexity?
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Approximation Algorithms for Independent Sets in Map Graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Map graphs
• Easy problems for tree-decomposable graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Fast and accurate algorithms for protein side-chain packing
• Polynomial Kernels for Hard Problems on Disk Graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Approximation algorithms for NP-complete problems on planar graphs
• Separators for sphere-packings and nearest neighbor graphs
• Handbook of Graph Grammars and Computing by Graph Transformation
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Robust algorithms for restricted domains
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Bidimensionality and Geometric Graphs
• Algorithms – ESA 2005