Undirected distances and the postman-structure of graphs

DOI10.1016/0095-8956(90)90062-5zbMath0638.05032OpenAlexW2136481365MaRDI QIDQ1099186

András Sebő

Publication date: 1990

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(90)90062-5

zbMATH Keywords

distancesweighted graphsmatchingsshortest pathsdistance functionChinese postman problemgood characterizationminimum weights of paths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (12)

Conservative weightings and ear-decompositions of graphs ⋮ A characterization of Seymour graphs ⋮ A characterization of minimal non-Seymour graphs ⋮ Packing $k$-Matchings and $k$-Critical Graphs ⋮ An Excluded Minor Characterization of Seymour Graphs ⋮ Tight integral duality gap in the Chinese postman problem ⋮ On shortest \(T\)-joins and packing \(T\)-cuts ⋮ Complexity of finding a join of maximum weight ⋮ Circuit decompositions of join-covered graphs ⋮ Graft analogue of general Kotzig-Lovász decomposition ⋮ Vertex set partitions preserving conservativeness ⋮ Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Brick decompositions and the matching rank of graphs
• Matching theory
• A quick proof of Seymour's theorem on t-joins
• The Schrijver system of odd join polyhedra
• Tight integral duality gap in the Chinese postman problem
• The matroids with the max-flow min-cut property
• Finding thet-join structure of graphs
• Covering directed and odd cuts
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• On Odd Cuts and Plane Multicommodity Flows
• 2-Matchings and 2-covers of hypergraphs
• Matching, Euler tours and the Chinese postman
• Paths, Trees, and Flowers
• On the structure of factorizable graphs

This page was built for publication: Undirected distances and the postman-structure of graphs