Top

Journal of Combinatorial Optimization

Published in:

01-07-2013

Critical edges/nodes for the minimum spanning tree problem: complexity and approximation

Authors: Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten

Published in: Journal of Combinatorial Optimization | Issue 1/2013

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

search-config

AI-assisted search

Off

Abstract

In this paper, we study the complexity and the approximation of the k most vital edges (nodes) and min edge (node) blocker versions for the minimum spanning tree problem (MST). We show that the k most vital edges MST problem is NP-hard even for complete graphs with weights 0 or 1 and 3-approximable for graphs with weights 0 or 1. We also prove that the k most vital nodes MST problem is not approximable within a factor n ^1−ϵ, for any ϵ>0, unless NP=ZPP, even for complete graphs of order n with weights 0 or 1. Furthermore, we show that the min edge blocker MST problem is NP-hard even for complete graphs with weights 0 or 1 and that the min node blocker MST problem is NP-hard to approximate within a factor 1.36 even for graphs with weights 0 or 1.

previous article Practical unicast and convergecast scheduling schemes for cognitive radio networks

next article Metric dimension of some distance-regular graphs

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 "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

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

Arora S, Lund C (1996) Hardness of approximations. In: Approximation algorithms for NP-hard problems. PWS Publishing Company, Boston, pp 399–446

Bar-Noy A, Khuller S, Schieber B (1995) The complexity of finding most vital arcs and nodes. Technical report CS-TR-3539, University of Maryland

Bazgan C, Toubaline S, Vanderpooten D (2010) Complexity of determining the most vital elements for the 1-median and 1-center location problems. In: Proceeding of the 4th annual international conference on combinatorial optimization and applications (COCOA 2010), Part I. LNCS, vol 6508, pp 237–251 CrossRef

Bazgan C, Toubaline S, Vanderpooten D (2011) Efficient algorithms for finding the k most vital edges for the minimum spanning tree problem. In: Proceeding of the 5th annual international conference on combinatorial optimization and applications (COCOA 2011). LNCS, vol 6831, pp 126–140 CrossRef

Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162(1):439–485 MathSciNetMATHCrossRef

Frederickson GN, Solis-Oba R (1996) Increasing the weight of minimum spanning trees. In: Proceedings of the 7th ACM-SIAM symposium on discrete algorithms (SODA 1996), pp 539–546. Also appeared in J Algorithms 33(2):244–266 (1999)

Håstad J (1999) Clique is hard to approximate within n ^1−ε. Acta Math 182(1):105–142 MathSciNetMATHCrossRef

Hsu L, Jan R, Lee Y, Hung C, Chern M (1991) Finding the most vital edge with respect to minimum spanning tree in a weighted graph. Inf Process Lett 39(5):277–281 MathSciNetMATHCrossRef

Iwano K, Katoh N (1993) Efficient algorithms for finding the most vital edge of a minimum spanning tree. Inf Process Lett 48(5):211–213 MathSciNetMATHCrossRef

Khachiyan L, Boros E, Borys K, Elbassioni K, Gurvich V, Rudolf G, Zhao J (2008) On short paths interdiction problems: total and node-wise limited interdiction. Theory Comput Syst 43(2):204–233 MathSciNetCrossRef

Khanna S, Motwani R, Sudan M, Vazirani U (1994) On syntactic versus computational views of approximability. In: Proceedings of the 35th annual IEEE annual symposium on foundations of computer science (FOCS 1994), pp 819–830. Also published in SIAM J Comput 28(1):164–191 (1999) CrossRef

Liang W (2001) Finding the k most vital edges with respect to minimum spanning trees for fixed k. Discrete Appl Math 113(2–3):319–327 MathSciNetMATHCrossRef

Liang W, Shen X (1997) Finding the k most vital edges in the minimum spanning tree problem. Parallel Comput 23(3):1889–1907 MathSciNetMATHCrossRef

Nardelli E, Proietti G, Widmayer P (2001) A faster computation of the most vital edge of a shortest path. Inf Process Lett 79(2):81–85 MathSciNetMATHCrossRef

Ratliff HD, Sicilia GT, Lubore SH (1975) Finding the n most vital links in flow networks. Manag Sci 21(5):531–539 MathSciNetMATHCrossRef

Shen H (1999) Finding the k most vital edges with respect to minimum spanning tree. Acta Inform 36(5):405–424 MathSciNetMATHCrossRef

Suraweera F, Maheshwari P, Bhattacharya P (1995) Optimal algorithms to find the most vital edge of a minimum spanning tree. Technical report CIT-95-21, School of Computing and Information Technology, Griffith University

Wollmer R (1964) Removing arcs from a network. Oper Res 12(6):934–940 MathSciNetMATHCrossRef

Wood RK (1993) Deterministic network interdiction. Math Comput Model 17(2):1–18 MATHCrossRef

Title: Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
Authors: Cristina Bazgan
Sonia Toubaline
Daniel Vanderpooten
Publication date: 01-07-2013
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2013
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-011-9449-4

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 "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2013

The three-dimensional matching problem in Kalmanson matrices

Optimal key tree structure for two-user replacement and deletion problems

Independent dominating sets in regular graphs

An adaptive multistart tabu search approach to solve the maximum clique problem

Parameterized complexity of k-anonymity: hardness and tractability

Maximum latency scheduling problem on two-person cooperative games

Premium Partner