2006/09/08 by Maxim A. Babenko, Babenko, Maxim A.
Computer Science · Engineering · Mathematics · #05C38 #05C40 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C38 #msc:05C40 #msc:05C75
paper · pdf · doi:10.48550/arxiv.math/0609221
16 pages, 5 figures
arxiv created 2006/09/08 · openalex publication_date 2006/09/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.