On the computational complexity of centers locating in a graph

DOI10.21136/am.1980.103883zbMath0454.68026OpenAlexW172960762MaRDI QIDQ3902477

Ján Plesník

Publication date: 1980

Full work available at URL: https://eudml.org/doc/15171

zbMATH Keywords

communication networksNP-completep-median problemm-center problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Related Items (17)

Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs ⋮ A heuristic for the p-center problem in graphs ⋮ On alternativep-center problems ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ The multi-service center problem ⋮ Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Approximation algorithm for the kinetic robust \(k\)-center problem ⋮ Deployment optimization of multi-hop wireless networks based on substitution graph ⋮ Improved approximability and non-approximability results for graph diameter decreasing problems ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ On interval and circular-arc covering problems ⋮ \(\mathsf{W[1}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension] ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• The Complexity of Near-Optimal Graph Coloring
• On the Computational Complexity of Combinatorial Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• P-Complete Approximation Problems
• R -Domination in Graphs
• Technical Note—An Algorithm for the p-Median Problem
• The Centers and Medians of a Graph
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph

This page was built for publication: On the computational complexity of centers locating in a graph