Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2015 | OriginalPaper | Chapter

Approximation Algorithms for k-Connected Graph Factors

Authors : Bodo Manthey, Marten Waanders

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all \(d \ge 2 \cdot \lceil k/2 \rceil \). For the case of k-vertex-connectedness, we achieve constant approximation ratios for \(d \ge 2k-1\). Our algorithms also work for arbitrary degree sequences if the minimum degree is at least \(2 \cdot \lceil k/2 \rceil \) (for k-edge-connectivity) or \(2k-1\) (for k-vertex-connectivity).

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
next chapter Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows
Literature
1.
Chan, Y.H., Fung, W.S., Lau, L.C., Yung, C.K.: Degree bounded network design with metric costs. SIAM J. Comput. 40(4), 953–980 (2011)MATHMathSciNetCrossRef
2.
3.
Cheriyan, J., Vempala, S., Vetta, A.: An approximation algorithm for the minimum-cost \(k\)-vertex connected subgraph. SIAM J. Comput. 32(4), 1050–1055 (2003)MATHMathSciNetCrossRef
4.
Cheriyan, J., Vetta, A.: Approximation algorithms for network design with metric costs. SIAM J. Discrete Math. 21(3), 612–636 (2007)MATHMathSciNetCrossRef
5.
Cornelissen, K., Hoeksma, R., Manthey, B., Narayanaswamy, N.S., Rahul, C.S.: Approximability of connected factors. In: Kaklamanis, C., Pruhs, K. (eds.) WAOA 2013. LNCS, vol. 8447, pp. 120–131. Springer, Heidelberg (2014)
6.
Czumaj, A., Lingas, A.: Minimum \(k\)-connected geometric networks. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 536–539. Springer, Heidelberg (2008)CrossRef
7.
Fekete, S.P., Khuller, S., Klemmstein, M., Raghavachari, B., Young, N.E.: A network-flow technique for finding low-weight bounded-degree spanning trees. J. Algorithms 24(2), 310–324 (1997)MATHMathSciNetCrossRef
8.
Fukunaga, T., Nagamochi, H.: Network design with edge-connectivity and degree constraints. Theor. Comput. Syst. 45(3), 512–532 (2009)MATHMathSciNetCrossRef
9.
10.
Fukunaga, T., Ravi, R.: Iterative rounding approximation algorithms for degree-bounded node-connectivity network design. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 263–272. IEEE Computer Society (2012)
11.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)MATH
12.
Goemans, M.X., Bertsimas, D.: Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. 60, 145–166 (1993)MATHMathSciNetCrossRef
13.
Kammer, F., Täubig, H.: Connectivity. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol. 3418, pp. 143–177. Springer, Heidelberg (2005) CrossRef
14.
Khandekar, R., Kortsarz, G., Nutov, Z.: On some network design problems with degree constraints. J. Comput. Syst. Sci. 79(5), 725–736 (2013)MATHMathSciNetCrossRef
15.
Khuller, S., Raghavachari, B.: Graph connectivity. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 371–373. Springer, Heidelberg (2008)CrossRef
16.
17.
18.
Lau, L.C., Naor, J., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints. SIAM J. Comput. 39(3), 1062–1087 (2009)MATHMathSciNetCrossRef
19.
Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. SIAM J. Comput. 42(6), 2217–2242 (2013)MATHMathSciNetCrossRef
20.
Lau, L.C., Zhou, H.: A unified algorithm for degree bounded survivable network design. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 369–380. Springer, Heidelberg (2014) CrossRef
21.
Lovász, L., Plummer, M.D.: Matching Theory, North-Holland Mathematics Studies, vol. 121. Elsevier (1986)
22.
Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM 62(1), 1:1–1:19 (2015)MathSciNetCrossRef
23.
24.
West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Upper Saddle River (2001)
25.
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2011)MATHCrossRef
26.
Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. In: Rayward-Smith, V.J. (ed.) Combinatorial Optimization II, Mathematical Programming Studies, vol. 13, pp. 121–134. Springer, Heidelberg (1980)CrossRef
Metadata
Title
Approximation Algorithms for k-Connected Graph Factors
Authors
Bodo Manthey
Marten Waanders
Copyright Year
2015
Book
Approximation and Online Algorithms

Print ISBN: 978-3-319-28683-9

Electronic ISBN: 978-3-319-28684-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-28684-6_1

Premium Partner

    Image Credits