Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
From MaRDI portal
Publication:2944488
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
Cited in
(59)- Recognizing map graphs of bounded treewidth
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- Guarding polyominoes under \(k\)-hop visibility
- Graph burning and non-uniform \(k\)-centers for small treewidth
- New algorithms for fair \(k\)-center problem with outliers and capacity constraints
- Vertex fusion under distance constraints
- On the \(k\)-hop domination numbers of spanning trees of unicyclic graphs
- Confronting intractability via parameters
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- Linearity of grid minors in treewidth with applications through bidimensionality
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
- Computing branchwidth via efficient triangulations and blocks
- A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Linear-time recognition of map graphs with outerplanar witness
- scientific article; zbMATH DE number 7278055 (Why is no real title available?)
- scientific article; zbMATH DE number 2038758 (Why is no real title available?)
- Approximation algorithm for the kinetic robust \(k\)-center problem
- Tree densities in sparse graph classes
- A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
- The Euclidean \(k\)-supplier problem in \(I R^2\)
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Decomposition of Map Graphs with Applications.
- Extended dynamic subgraph statistics using \(h\)-index parameterized data structures
- A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree
- Implicit branching and parameterized partial cover problems
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- A linear time algorithm for optimal \(k\)-hop dominating set of a tree
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Constrained representations of map graphs and half-squares
- Augmenting outerplanar graphs to meet diameter requirements
- Map graphs having witnesses of large girth
- Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
- Subexponential fixed-parameter algorithms for partial vector domination
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- On complexities of minus domination
- Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
- Subexponential parameterized algorithms for graphs of polynomial growth
- New results on directed edge dominating set
- New analysis and computational study for the planar connected dominating set problem
- Subexponential parameterized algorithms
- Structure of graphs with locally restricted crossings
- (Total) vector domination for graphs with bounded branchwidth
- Subexponential fixed-parameter algorithms for partial vector domination
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Bidimensionality and kernels
- Progressive algorithms for domination and independence
- Approximation algorithms via contraction decomposition
- Local search: is brute-force avoidable?
- Orthogonal tree decompositions of graphs
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- The parameterized hardness of the \(k\)-center problem in transportation networks
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)
