scientific article; zbMATH DE number 16725

MaRDI QIDQ3973411zbMATH OpenFDO

Authors Francisco Barahona

Publication date 26 June 1992

zbMATH Keywords

Chinese Postman Problemmax cutmulticommodity flow

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Tight integral duality gap in the Chinese postman problem
• On multicommodity flows in planar graphs
• Flow in Planar Graphs with Multiple Sources and Sinks
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks

Cited in

(14)

• Undirected distances and the postman-structure of graphs
• Tight integral duality gap in the Chinese postman problem
• An algorithm for min-cost edge-disjoint cycles and its applications
• A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• On dual integrality in matching problems
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• On multicommodity flows in planar graphs
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• On matchings, T‐joins, and arc routing in road networks
• On cuts and matchings in planar graphs
• Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\)

This page was built for publication:

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