Graph Orientations with Edge-connection and Parity Constraints |
| |
Authors: | András Frank Zoltán Király |
| |
Institution: | 1.Department of Operations Research, E?tv?s University; Pázmány Péter sétány 1/c, Budapest, Hungary, H-1117; and Traffic Lab, Ericsson Hungary; Laborc u. 1, Budapest, Hungary H-1037; E-mail: frank@cs.elte.hu,HU;2.Department of Computer Science, E?tv?s University; Pázmány Péter sétány 1/c, Budapest, Hungary, H-1117; and Traffic Lab, Ericsson Hungary; Laborc u. 1, Budapest, Hungary H-1037; E-mail: kiraly@cs.elte.hu,HU |
| |
Abstract: | Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt
to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed.
The main result is a characterization of undirected graphs G = (V,E) having a k-edge-connected T-odd orientation for every subset with |E| + |T| even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k)-edge-connected graph with |V| + |E| even has a (k-1)-edge-connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will
be given for digraphs with a root-node s having k edge-disjoint paths from s to every node and k-1 edge-disjoint paths from every node to s.
Received December 14, 1998/Revised January 12, 2001
RID="*"
ID="*" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772. Part of research was done while
this author was visiting EPFL, Lausanne, June, 1998.
RID="†"
ID="†" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772 and OTKA T030059. |
| |
Keywords: | AMS Subject Classification (2000) Classes: 05C75 05C40 |
本文献已被 SpringerLink 等数据库收录! |
|