التفاصيل البيبلوغرافية
| العنوان: |
On the complexity of the vector connectivity problem. |
| المؤلفون: |
Cicalese, Ferdinando1 ferdinando.cicalese@univr.it, Milanič, Martin2,3 martin.milanic@upr.si, Rizzi, Romeo1 romeo.rizzi@univr.it |
| المصدر: |
Theoretical Computer Science. Aug2015, Vol. 591, p60-71. 12p. |
| مصطلحات موضوعية: |
*VECTOR dominance model, *DOMINATING set, *CARDINAL numbers, *GEOMETRIC vertices, *POLYNOMIAL time algorithms, *BIPARTITE graphs |
| مستخلص: |
We study a relaxation of the Vector Domination problem called Vector Connectivity ( VecCon ). Given a graph G with a requirement r ( v ) for each vertex v , VecCon asks for a minimum cardinality set S of vertices such that every vertex v ∈ V ∖ S is connected to S via r ( v ) disjoint paths. In the paper introducing the problem, Boros et al. [4] gave polynomial-time solutions for VecCon in trees, cographs, and split graphs, and showed that the problem can be approximated in polynomial time on n -vertex graphs to within a factor of log n + 2 , leaving open the question of whether the problem is NP -hard on general graphs. We show that VecCon is APX -hard in general graphs, and NP -hard in planar bipartite graphs and in planar line graphs. We also generalize the polynomial result for trees by solving the problem for block graphs. [ABSTRACT FROM AUTHOR] |
| قاعدة البيانات: |
Academic Search Index |
Full Text Finder