An algorithm for min-cost edge-disjoint cycles and its applications

DOI10.1016/0167-6377(92)90102-9zbMath0767.90089OpenAlexW2029453727MaRDI QIDQ1200787

Sun Wu, Udi Manber

Publication date: 16 January 1993

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90102-9

zbMATH Keywords

planar graphsmaximum cutweighted undirected graphchinese postman problemedge-disjoint cyclesmax-weight matchingnegative costs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel concepts in graph theory
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Applications of a Planar Separator Theorem
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• A graph-theoretic via minimization algorithm for two-layer printed circuit boards
• Matching, Euler tours and the Chinese postman
• Unifying maximum cut and minimum cut of a planar graph
• Shortest path algorithms using dynamic breadth‐first search

This page was built for publication: An algorithm for min-cost edge-disjoint cycles and its applications