A strongly polynomial algorithm for the minimum cost tension problem

DOI10.1016/S0012-365X(96)00185-9zbMath0873.90101WikidataQ127646320 ScholiaQ127646320MaRDI QIDQ1356759

Malika Hadjiat, Jean-Francois Maurras

Publication date: 30 October 1997

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

zbMATH Keywords

strongly polynomial algorithmminimum cost tension problemmin-mean-cost residual cut problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (6)

An analysis of the parameterized complexity of periodic timetabling ⋮ A faster strongly polynomial time algorithm to solve the minimum cost tension problem ⋮ Penelope's graph: a hard minimum cost tension instance ⋮ An \(O(n(m+n\log n)\log n)\) time algorithm to solve the minimum cost tension problem ⋮ An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem ⋮ Aggregation approach for the minimum binary cost tension problem

Cites Work

• A strongly polynomial minimum cost circulation algorithm
• A characterization of the minimum cycle mean in a digraph
• Finding minimum-cost circulations by canceling negative cycles
• Minimum cuts, modular functions, and matroid polyhedra
• Miu Cost Tensions
• Flots et tensions dans un graphe
• An “out-of-kilter” algorithm for solving minimum cost potential problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A strongly polynomial algorithm for the minimum cost tension problem