Sharp bounds for the Chinese postman problem in 3-regular graphs and multigraphs

DOI10.1016/J.DAM.2015.03.017MaRDI QIDQ2352793zbMATH OpenOpenAlexFDO

Authors Suil O, Douglas B. West

Publication date 6 July 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.03.017

zbMATH Keywords

Chinese postman problemregular graphparity subgraphballoon

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Recommendations

• Chinese postman problem on edge-colored multigraphs
• Covering the edges of a graph by circuits
• On the length of the Chinese postman tour in homogeneous graphs
• scientific article; zbMATH DE number 3880464
• scientific article; zbMATH DE number 4211828

Cites work

• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
• Maximum matching and a polyhedron with 0,1-vertices
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Shortest coverings of graphs with cycles

Cited in

(5)

• Largest 2-regular subgraphs in 3-regular graphs
• On the length of the Chinese postman tour in homogeneous graphs
• An updated annotated bibliography on arc routing problems
• Graphs inducing totally balanced and submodular Chinese postman games
• Hierarchical Chinese postman problem with fuzzy travel times

This page was built for publication: Sharp bounds for the Chinese postman problem in 3-regular graphs and multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2352793)