**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Graph orientations with edge-connection and parity constraints

2001

Journal paper

Journal paper

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications

No results

Related concepts (9)

Combinatorial optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or ca

Matching (graph theory)

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matchi

Eulerian path

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian