Title :
NP-Completeness of the minimum edge-ranking spanning tree problem on series-parallel graphs
Author :
Arefin, A.S. ; Kashem Mia, M.A.
Author_Institution :
Inst. of Inf. & Commun. Technol., BUET, Dhaka
Abstract :
The minimum edge-ranking spanning tree (MERST) problem on a graph is to find a spanning tree of G whose edge-ranking needs least number of ranks. Although polynomial-time algorithm to solve the minimum edge-ranking spanning tree problem on series-parallel graphs with bounded degrees has been found, but for the unbounded degrees no polynomial-time algorithm is known. In this paper, we prove that the minimum edge-ranking spanning tree problem on general series-parallel graph is NP-complete.
Keywords :
computational complexity; series (mathematics); trees (mathematics); MERST problem; NP-completeness; minimum edge-ranking spanning tree problem; polynomial-time algorithm; series-parallel graphs; Assembly; Communications technology; Labeling; Merging; Polynomials; Relational databases; Tree graphs; Algorithm; NP-Completeness; edge-ranking; series-parallel graph; spanning tree;
Conference_Titel :
Computer and information technology, 2007. iccit 2007. 10th international conference on
Conference_Location :
Dhaka
Print_ISBN :
978-1-4244-1550-2
Electronic_ISBN :
978-1-4244-1551-9
DOI :
10.1109/ICCITECHN.2007.4579371
