Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
From MaRDI portal
Publication:2944488
DOI10.1145/1077464.1077468zbMATH Open1321.05256OpenAlexW2007069176MaRDI QIDQ2944488FDOQ2944488
Authors: Erik D. Demaine, Fedor V. Fomin, Dimitrios M. Thilikos, Mohammad T. Hajiaghayi 
Publication date: 2 September 2015
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.6569
Recommendations
- scientific article; zbMATH DE number 2038758
- Approximating \(k\)-center in planar graphs
- An Algorithm for the p-Center Problem in the Plane
- scientific article; zbMATH DE number 7278055
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- An approximation algorithm for \(k\)-center problem on a convex polygon
- A near-linear algorithm for the planar 2-center problem
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)
Cited In (62)
- Title not available (Why is that?)
- Graph burning and non-uniform \(k\)-centers for small treewidth
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- Recognizing map graphs of bounded treewidth
- Guarding polyominoes under \(k\)-hop visibility
- New algorithms for fair \(k\)-center problem with outliers and capacity constraints
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Hardness and structural results for half-squares of restricted tree convex bipartite graphs
- Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
- Title not available (Why is that?)
- Linearity of grid minors in treewidth with applications through bidimensionality
- Title not available (Why is that?)
- Approximation algorithm for the kinetic robust \(k\)-center problem
- Bidimensionality and Kernels
- A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
- Augmenting outerplanar graphs to meet diameter requirements
- Subexponential fixed-parameter algorithms for partial vector domination
- (Total) vector domination for graphs with bounded branchwidth
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Structure of Graphs with Locally Restricted Crossings
- Map graphs having witnesses of large girth
- Computing branchwidth via efficient triangulations and blocks
- Extended dynamic subgraph statistics using \(h\)-index parameterized data structures
- Implicit branching and parameterized partial cover problems
- Parameterized approximation algorithms for some location problems in graphs
- Tree densities in sparse graph classes
- Subexponential parameterized algorithms for graphs of polynomial growth
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
- New analysis and computational study for the planar connected dominating set problem
- New Results on Directed Edge Dominating Set
- Linear-time recognition of map graphs with outerplanar witness
- The Euclidean \(k\)-supplier problem in \(I R^2\)
- Subexponential parameterized algorithms
- Confronting intractability via parameters
- Stack and Queue Layouts via Layered Separators
- A linear time algorithm for optimal \(k\)-hop dominating set of a tree
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
- Title not available (Why is that?)
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Approximation algorithms via contraction decomposition
- Vertex fusion under distance constraints
- Orthogonal Tree Decompositions of Graphs
- A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- The Parameterized Hardness of the k-Center Problem in Transportation Networks
- Title not available (Why is that?)
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Subexponential Fixed-Parameter Algorithms for Partial Vector Domination
- A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
- Decomposition of Map Graphs with Applications.
- Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
- Local search: is brute-force avoidable?
- On Complexities of Minus Domination
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Title not available (Why is that?)
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
This page was built for publication: Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944488)
