Back to Search
Start Over
ALGORITHMS FOR FINDING A MAXIMUM NON-k-LINKED GRAPH.
- Source :
-
SIAM Journal on Discrete Mathematics . 2012, Vol. 26 Issue 2, p591-604. 14p. 5 Diagrams, 1 Chart. - Publication Year :
- 2012
-
Abstract
- A graph with at least 2k vertices is said to be k-linked if for any two ordered k-tuples (s1,…, sk) and (t1,…,tk) of 2k distinct vertices, there exist pairwise vertex-disjoint paths P1,…,Pk such that Pi connects si and ti for i = 1,…,k. For a given graph G, we consider the problem of finding a maximum induced subgraph of G that is not k-linked. This problem is a common generalization of computing vertex-connectivity and testing k-linkedness of G, and it is closely related to the concept of H-linkedness. In this paper, we give the first polynomial-time algorithm for the case of k = 2, whereas a similar problem to find a maximum induced subgraph without 2-vertex-disjoint paths connecting fixed terminal pairs is NP-hard. For the case of general k, we give an (8k -- 2)-additive approximation algorithm. We also investigate the computational complexity of the edge-disjoint case and the directed case. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 26
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 80535691
- Full Text :
- https://doi.org/10.1137/110846725