Top

Published in:

2017 | OriginalPaper | Chapter

Parameterized Approximation Algorithms for Some Location Problems in Graphs

Authors : Arne Leitert, Feodor F. Dragan

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) r-Domination problem and the (Connected) p-Center problem for unweighted and undirected graphs. Given a graph G, we show how to construct a (connected) \(\big (r + \mathcal {O}(\mu ) \big )\)-dominating set D with \(|D| \le |D^*|\) efficiently. Here, \(D^*\) is a minimum (connected) r-dominating set of G and \(\mu \) is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of G. Additionally, we show that a \(+ \mathcal {O}(\mu )\)-approximation for the (Connected) p-Center problem on G can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach

next chapter Approximation Algorithms for Maximum Coverage with Group Budget Constraints

Abboud, A., Williams, V.V., Wang, J.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 377–391 (2016)

Abu-Ata, M., Dragan, F.F.: Metric tree-like structures in real-life networks: an empirical study. Networks 67(1), 49–68 (2016)CrossRefMathSciNet

Brandstädt, A., Chepoi, V., Dragan, F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Appl. Math. 82(1–3), 43–77 (1998)CrossRefMATHMathSciNet

Brandstädt, A., Chepoi, V., Dragan, F.F.: Distance approximating trees for chordal and dually chordal graphs. J. Algorithms 30, 166–184 (1999)CrossRefMATHMathSciNet

Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D., Trevisan, D.: From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More Manuscript, CoRR abs/1708.04218 (2017)

Chen, Y., Lin, B.: The Constant Inapproximability of the Parameterized Dominating Set Problem, Manuscript, CoRR abs/1511.00075 (2015)

Chepoi, V., Dragan, F.F.: A note on distance approximating trees in graphs. Eur. J. Comb. 21, 761–766 (2000)CrossRefMATHMathSciNet

Chepoi, V.D., Dragan, F.F., Estellon, B., Habib, M., Vaxes, Y.: Diameters, centers, and approximating trees of \(\delta \)-hyperbolic geodesic spaces and graphs. In: Proceedings of the 24th Annual ACM Symposium on Computational Geometry, SoCG 2008, pp. 59–68 (2008)

Chepoi, V., Estellon, B.: Packing and covering \(\delta \)-hyperbolic spaces by balls. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX/RANDOM -2007. LNCS, vol. 4627, pp. 59–73. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74208-1_5 CrossRef

10.

Chlebík, M., Chlebíková, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206, 1264–1275 (2008)CrossRefMATHMathSciNet

11.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)MATH

12.

Dourisboure, Y., Dragan, F.F., Gavoille, C., Yan, C.: Spanners for bounded tree-length graphs. Theor. Comput. Sci. 383(1), 34–44 (2007)CrossRefMATHMathSciNet

13.

Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)CrossRefMATH

14.

Dragan, F.F.: HT-graphs: centers, connected \(r\)-domination and Steiner trees. Comput. Sci. J. Moldova 1(2), 64–83 (1993)MathSciNet

15.

Edwards, K., Kennedy, S., Saniee, I.: Fast approximation algorithms for p-centers in large \(\delta \)-hyperbolic graphs. In: Bonato, A., Graham, F.C., Prałat, P. (eds.) WAW 2016. LNCS, vol. 10088, pp. 60–73. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49787-7_6 CrossRef

16.

Escoffier, B., Paschos, V.T.: Completeness in approximation classes beyond APX. Theor. Comput. Sci. 359(1–3), 369–377 (2006)CrossRefMATHMathSciNet

17.

Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293–306 (1985)CrossRefMATHMathSciNet

18.

Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)CrossRefMATHMathSciNet

19.

Leitert, A., Dragan, F.F.: Parametrized Approximation Algorithms for some Location Problems in Graphs, Manuscript, CoRR abs/1706.07475 (2017)

20.

Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)CrossRefMATH

21.

Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 475–484 (1997)

22.

Yen, W.C.-K., Chen, C.-T.: The \(p\)-center problem with connectivity constraint. Appl. Math. Sci. 1(27), 1311–1324 (2007)MATHMathSciNet

Title: Parameterized Approximation Algorithms for Some Location Problems in Graphs
Authors: Arne Leitert
Feodor F. Dragan
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-71146-1

Electronic ISBN: 978-3-319-71147-8

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-71147-8_24

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner