On Ear Decompositions of Strongly Connected Bidirected Graphs

Bidirected graphs (earlier studied by Edmonds, Johnson and, in equivalent terms of skew-symmetric graphs, by Tutte, Goldberg, Karzanov, and others) proved to be a useful unifying language for describing both flow and matching problems. In this paper we extend the notion of ear decomposition to the c...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2006-09
Main Author: Babenko, Maxim A
Format: Article
Language:English
Subjects:
Decomposition
Graph matching
Graphs
Theorems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Bidirected graphs (earlier studied by Edmonds, Johnson and, in equivalent terms of skew-symmetric graphs, by Tutte, Goldberg, Karzanov, and others) proved to be a useful unifying language for describing both flow and matching problems. In this paper we extend the notion of ear decomposition to the class of strongly connected bidirected graphs. In particular, our results imply Two Ear Theorem on matching covered graphs of Lovász and Plummer. The proofs given here are self-contained except for standard Barrier Theorem on skew-symmetric graphs.
ISSN:2331-8422