Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Parameterized complexity, tractability and kernelization (68Q27)
- scientific article; zbMATH DE number 2119747 (Why is no real title available?)
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- A polylogarithmic approximation of the minimum bisection
- A polynomial-time bicriteria approximation scheme for planar bisection
- A study on two geometric location problems
- A subset spanner for Planar graphs, with application to subset TSP
- Algorithms and Data Structures
- An Efficient Heuristic Procedure for Partitioning Graphs
- An FPT algorithm beating 2-approximation for \(k\)-cut
- Approximating the minimum bisection size (extended abstract)
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms via contraction decomposition
- Approximation schemes for covering and packing problems in image processing and VLSI
- Computing cut-based hierarchical decompositions in almost linear time
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- Designing FPT algorithms for cut problems using randomized contractions
- Diameter and treewidth in minor-closed graph families
- Exact combinatorial branch-and-bound for graph bisection
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Faster exact and approximate algorithms for k-cut
- Finding small separators in linear time via treewidth reduction
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Fine-grained complexity of coloring unit disks and balls
- Fundamentals of parameterized complexity
- Geometric separator theorems and applications
- Minimum bisection is NP-hard on unit disk graphs
- Minimum bisection is fixed parameter tractable
- Minimum clique partition in unit disk graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Parameterized algorithms
- Partitioning Planar Graphs
- Polynomial kernels for hard problems on disk graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The minimum k-way cut of bounded size is fixed-parameter tractable
- Thin graph classes and polynomial-time approximation schemes
- Unit disk graphs
This page was built for publication: Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023564)
