1. PACKING EDGE-DISJOINT ODD EULERIAN SUBGRAPHS THROUGH PRESCRIBED VERTICES IN 4-EDGE-CONNECTED GRAPHS.
- Author
-
NAONORI KAKIMURA, KEN-ICHI KAWARABAYASHI, and YUSUKE KOBAYASHI
- Subjects
- *
EULERIAN graphs , *GRAPH theory , *MATHEMATICAL proofs , *ALGORITHMS , *GEOMETRIC vertices - Abstract
In this paper, we show the Erdős-Pósa property for edge-disjoint packing of S-closed walks with parity constraints in 4-edge-connected graphs. More precisely, we prove that for any 4-edge-connected graph G and any vertex subset S, either G h as k edge-disjoint elementary closed odd walks, each of which has at least one vertex of S, or G has an edge set F with |F| < f (k) such that G - F has no such walks. The 4-edge-connectivity is the best possible in the sense that 3-edge-connected graphs do not satisfy the statement. Since the proof is constructive, we can design a fixed-parameter algorithm for finding k edge-disjoint walks satisfying the conditions in a 4-edge-connected graph for a parameter k. In addition, this gives a simple fixed-parameter algorithm for the parity edge-disjoint walks problem with k terminal pairs. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF