Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
From MaRDI portal
Publication:2944488
DOI10.1145/1077464.1077468zbMath1321.05256OpenAlexW2007069176MaRDI QIDQ2944488
Dimitrios M. Thilikos, Fedor V. Fomin, Erik D. Demaine, Mohammad Taghi 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
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, (Total) vector domination for graphs with bounded branchwidth, Tree densities in sparse graph classes, An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs, Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs, Map graphs having witnesses of large girth, Parameterized Complexity for Domination Problems on Degenerate Graphs, New analysis and computational study for the planar connected dominating set problem, Subexponential Fixed-Parameter Algorithms for Partial Vector Domination, Linear-time recognition of map graphs with outerplanar witness, A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph, Unnamed Item, The Euclidean \(k\)-supplier problem in \(I R^2\), New Results on Directed Edge Dominating Set, A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree, The parameterized hardness of the \(k\)-center problem in transportation networks, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Structure of Graphs with Locally Restricted Crossings, Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems, A linear time algorithm for optimal \(k\)-hop dominating set of a tree, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, A parameterized approximation algorithm for the multiple allocation \(k\)-hub center, Stack and Queue Layouts via Layered Separators, Graph burning and non-uniform \(k\)-centers for small treewidth, Recognizing map graphs of bounded treewidth, Approximation algorithms via contraction decomposition, Local search: is brute-force avoidable?, Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier, Extended dynamic subgraph statistics using \(h\)-index parameterized data structures, Unnamed Item, Subexponential parameterized algorithms, Confronting intractability via parameters, Implicit branching and parameterized partial cover problems, Orthogonal Tree Decompositions of Graphs, Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs, Linearity of grid minors in treewidth with applications through bidimensionality, Subexponential fixed-parameter algorithms for partial vector domination, Computing branchwidth via efficient triangulations and blocks, Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm, Approximation algorithm for the kinetic robust \(k\)-center problem, Unnamed Item, Unnamed Item, Parameterized approximation algorithms for some location problems in graphs, Hardness and structural results for half-squares of restricted tree convex bipartite graphs, Bidimensionality and Kernels, Decomposition of Map Graphs with Applications., Unnamed Item, Vertex fusion under distance constraints, Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor, Subexponential parameterized algorithms for graphs of polynomial growth, The Parameterized Hardness of the k-Center Problem in Transportation Networks, Unnamed Item, Unnamed Item, Augmenting Outerplanar Graphs to Meet Diameter Requirements, On Complexities of Minus Domination
