Bisecting a 4-connected graph with three resource sets
| Autor: | Toshimasa Ishii, Hiroshi Nagamochi, Kengo Iwata |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Discrete mathematics
Conjecture Graph connectivity Applied Mathematics Graph algorithm Complete graph Partition problem Disjoint sets Combinatorics Convex polytope Supporting hyperplane Discrete Mathematics and Combinatorics Partition (number theory) Connectivity Graph partition problem Embedding Mathematics |
| Zdroj: | Discrete Applied Mathematics. 155:1441-1450 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2007.03.004 |
| Popis: | Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T"1,T"2,...,T"k of nodes, called resource sets, where |T"i| is even for each i. The partition problem with k resource sets asks to find a partition V"1 and V"2 of the node set V such that the graphs induced by V"1 and V"2 are both connected and |V"[email protected]?T"i|=|V"[email protected]?T"i|=|T"i|/2 holds for each i=1,2,...,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k>=3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has K"4 as its subgraph, then a bisection exists and it can be found in O(|V|^3log|V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect