Decomposition of Map Graphs with Applications.
From MaRDI portal
Publication:5091217
DOI10.4230/LIPIcs.ICALP.2019.60OpenAlexW2956506328MaRDI QIDQ5091217
Meirav Zehavi, Saket Saurabh, Daniel Lokshtanov, Fahad Panolan, Fedor V. Fomin
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1903.01291
Related Items (3)
Clique-based separators for geometric intersection graphs ⋮ Faster algorithms for cycle hitting problems on disk graphs ⋮ Recognizing map graphs of bounded treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linearity of grid minors in treewidth with applications through bidimensionality
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Quickly excluding a planar graph
- Which problems have strongly exponential complexity?
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Narrow sieves for parameterized paths and packings
- Recognizing hole-free 4-map graphs in cubic time
- Approximation Algorithms for Independent Sets in Map Graphs
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Map graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Faster Algebraic Algorithms for Path and Packing Problems
- Approximation algorithms for NP-complete problems on planar graphs
- Color-coding
- Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes
- Quick k-Median, k-Center, and Facility Location for Sparse Graphs
- Parameterized complexity: exponential speed-up for planar graph problems
- LIMITS and Applications of Group Algebras for Parameterized Problems
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
This page was built for publication: Decomposition of Map Graphs with Applications.