scientific article; zbMATH DE number 7053376
From MaRDI portal
Publication:5743499
zbMATH Open1421.68126MaRDI QIDQ5743499FDOQ5743499
Authors: 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 of this publication is not available (Why is that?)
Recommendations
- Bidimensionality of geometric intersection graphs
- Contraction-bidimensionality of geometric intersection graphs
- Contraction bidimensionality of geometric intersection graphs
- scientific article; zbMATH DE number 1342089
- Geometric representations of graphs
- Geometric representations of graphs
- scientific article; zbMATH DE number 1943970
- Geometrical embeddings of graphs
- Bilinear maps and graphs
- Geometric graphs
treewidthexponential time hypothesisfixed-parameter tractabilitysubexponential algorithmbidimensionalityEPTASexcluded grid theoremunit-disc graphmap graph
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Graph searching and a min-max theorem for tree-width
- Some APX-completeness results for cubic graphs
- Unit disk graphs
- A partial k-arboretum of graphs with bounded treewidth
- Which problems have strongly exponential complexity?
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- Quickly excluding a planar graph
- Bidimensionality and kernels
- Handbook of Graph Grammars and Computing by Graph Transformation
- Three-dimensional orthogonal graph drawing algorithms
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Separators for sphere-packings and nearest neighbor graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Title not available (Why is that?)
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Simple heuristics for unit disk graphs
- Algorithms – ESA 2005
- Polynomial-time approximation schemes for packing and piercing fat objects
- Approximation algorithms for independent sets in map graphs
- Map graphs
- Title not available (Why is that?)
- Linearity of grid minors in treewidth with applications through bidimensionality
- Label placement by maximum independent set in rectangles
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Minimum clique partition in unit disk graphs
- Robust algorithms for restricted domains
- Fast and accurate algorithms for protein side-chain packing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial kernels for hard problems on disk graphs
Cited In (33)
- Coverability and sub-exponential parameterized algorithms in planar graphs
- A Retrospective on (Meta) Kernelization
- Faster algorithms for cycle hitting problems on disk graphs
- Contraction bidimensionality of geometric intersection graphs
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Clustered 3-colouring graphs of bounded degree
- Orthogonal tree decompositions of graphs
- Computing list homomorphisms in geometric intersection graphs
- Optimality program in segment and string graphs
- Graph product structure for non-minor-closed classes
- On embeddability of unit disk graphs onto straight lines
- Bidimensionality of geometric intersection graphs
- Excluded grid minors and efficient polynomial-time approximation schemes
- Contraction-bidimensionality of geometric intersection graphs
- Map graphs having witnesses of large girth
- Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
- Tree densities in sparse graph classes
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Title not available (Why is that?)
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- Recognizing map graphs of bounded treewidth
- Constrained representations of map graphs and half-squares
- Bidimensionality and kernels
- Linear-time recognition of map graphs with outerplanar witness
- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
- Structure of graphs with locally restricted crossings
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Notes on graph product structure theory
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Decomposition of Map Graphs with Applications.
- Title not available (Why is that?)
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743499)
