DocumentCode :
2644983
Title :
Approximating minimum-size k-connected spanning subgraphs via matching
Author :
Cheriyan, Joseph ; Thurimella, Ramakrishna
Author_Institution :
Dept. of Combinatorics & Optimization, Waterloo Univ., Ont., Canada
fYear :
1996
fDate :
14-16 Oct 1996
Firstpage :
292
Lastpage :
301
Abstract :
An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of a given (undirected or directed) graph G=(V,E). There are four versions of the problem, depending on whether G is undirected or directed, and whether the spanning subgraph is required to be k-node connected (k-NCSS) or k-edge connected (k-ECSS). The approximation guarantees are as follows: min-size k-NCSS of an undirected graph 1+[1/k], min-size k-NCSS of a directed graph 1+[1/k], min-size k-ECSS of an undirected graph 1+[7/k], & min-size k-ECSS of a directed graph 1+[4/√k]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple, deterministic, and runs in time O(k|E|2). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or a-edge connected) spanning subgraph whose size is within a factor of (1.5+ε) of minimum, where ε>0 is a constant
Keywords :
computational complexity; graph theory; pattern matching; heuristic; k-ECSS; k-NCSS; k-connected spanning subgraphs; matching; minimum-size; undirected graphs; Approximation algorithms; Computer science; Fasteners; Optimized production technology; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
Conference_Location :
Burlington, VT
ISSN :
0272-5428
Print_ISBN :
0-8186-7594-2
Type :
conf
DOI :
10.1109/SFCS.1996.548488
Filename :
548488
Link To Document :
بازگشت