The line index and minimum cut of weighted graphs

DOI10.1016/S0377-2217(97)00196-3zbMath0972.05026MaRDI QIDQ1303736

Shao-Ji Xu

Publication date: 13 November 2001

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

minimum cutweighted graphsplanar graphseries-parallel graphbalanced graphlinear algorithmsline indexminimum capacity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35)

Related Items (3)

On tail dependence matrices. The realization problem for parametric families ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ On optimization of complete social networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• An algorithm for identifying Morishima and anti-Morishima matrices and balanced digraphs
• Balancing signed graphs
• Weakly bipartite graphs and the max-cut problem
• A simple algorithm to detect balance in signed graphs
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Some simplified NP-complete graph problems
• Parallel concepts in graph theory
• Topology of series-parallel networks
• On some extremal problems in graph theory
• On the notion of balance of a signed graph
• Maximal Flow Through a Network
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Comments on F. Hadlock’s Paper: “Finding a Maximum Cut of a Planar Graph in Polynomial Time”
• Unifying maximum cut and minimum cut of a planar graph

This page was built for publication: The line index and minimum cut of weighted graphs