Minimum convex piecewise linear cost tension problem on quasi-\(k\) series-parallel graphs

DOI10.1007/S10288-004-0049-3zbMath1112.90087OpenAlexW1995845603MaRDI QIDQ1775289

Bruno Bachelet, Philippe Mahey

Publication date: 6 May 2005

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-004-0049-3

zbMATH Keywords

graph decompositionout-of-kilter algorithmMinimum cost tensionseries-parallel recognitiontwo-terminal series-parallel digraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A faster strongly polynomial time algorithm to solve the minimum cost tension problem ⋮ 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

This page was built for publication: Minimum convex piecewise linear cost tension problem on quasi-\(k\) series-parallel graphs