Undirected distances and the postman-structure of graphs

DOI10.1016/0095-8956(90)90062-5zbMath0638.05032MaRDI 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

distances; weighted graphs; matchings; shortest paths; distance function; Chinese postman problem; good characterization; minimum weights of paths

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

90B10: Deterministic network models in operations research

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

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

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