Minimum convex-cost tension problems on series-parallel graphs
RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 4, p. 221-234

We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in $O\left({m}^{3}\right)$ operations.

DOI : https://doi.org/10.1051/ro:2004202
Keywords: minimum cost tension, convex piecewise linear costs, series-parallel graphs
@article{RO_2003__37_4_221_0,
author = {Bachelet, Bruno and Mahey, Philippe},
title = {Minimum convex-cost tension problems on series-parallel graphs},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
publisher = {EDP-Sciences},
volume = {37},
number = {4},
year = {2003},
pages = {221-234},
doi = {10.1051/ro:2004202},
zbl = {1101.68715},
mrnumber = {2064599},
language = {en},
url = {http://www.numdam.org/item/RO_2003__37_4_221_0}
}

Bachelet, Bruno; Mahey, Philippe. Minimum convex-cost tension problems on series-parallel graphs. RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 4, pp. 221-234. doi : 10.1051/ro:2004202. http://www.numdam.org/item/RO_2003__37_4_221_0/

[1] R.K. Ahuja, D.S. Hochbaum and J.B. Orlin, Solving the Convex Cost Integer Dual Network Flow Problem. Lect. Notes Comput. Sci. 1610 (1999) 31-44. | MR 1709370 | Zbl 0948.90116

[2] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows - Theory, Algorithms, and Applications. Prentice Hall (1993).

[3] J.F. Allen, Maintaining Knowledge about Temporal Intervals. Commun. ACM 26 (1983) 832-843. | Zbl 0519.68079

[4] B. Bachelet, B++ Library. http://frog.isima.fr/bruno/?doc=bpp_library

[5] B. Bachelet and P. Mahey, Optimisation de la présentation d'un document hypermédia. Ann. Sci. Univ. Blaise Pascal 110 (2001) 81-90.

[6] B. Bachelet, P. Mahey, R. Rodrigues and L.F. Soares, Elastic Time Computation for Hypermedia Documents. SBMidìa (2000) 47-62 .

[7] C. Berge and A. Ghoula-Houri, Programmes, jeux et réseaux de transport. Dunod (1962). | MR 192912 | Zbl 0111.17302

[8] M.W. Bern, E.L. Lawler and A.L. Wong, Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs. J. Algorithms 8 (1987) 216-235. | MR 890873 | Zbl 0618.68058

[9] M.C. Buchanan and P.T. Zellweger, Specifying Temporal Behavior in Hypermedia Documents. Eur. Conference on Hypertext '92 (1992) 262-271.

[10] M.C. Buchanan and P.T. Zellweger, Automatically Generating Consistent Schedules for Multimedia Documents. Multimedia Systems (1993) 55-67.

[11] A.K. Datta and R.K. Sen, An Efficient Scheme to Solve Two Problems for Two-Terminal Series Parallel Graphs. Inform. Proc. Lett. 71 (1999) 9-15. | MR 1711638 | Zbl 1005.68998

[12] R.J. Duffin, Topology of Series-Parallel Networks. J. Math. Anal. Appl. 10 (1965) 303-318. | MR 175809 | Zbl 0128.37002

[13] D. Eppstein, Parallel Recognition of Series-Parallel Graphs. Inform. Comput. 98 (1992) 41-55. | MR 1161075 | Zbl 0754.68056

[14] D.R. Fulkerson, An Out-of-Kilter Method for Minimal Cost Flow Problems. SIAM J. Appl. Math. 9 (1961) 18-27. | Zbl 0112.12401

[15] M. Hadjiat, Penelope's Graph: a Hard Minimum Cost Tension Instance. Theoret. Comput. Sci. 194 (1998) 207-218. | Zbl 0912.68007

[16] C.W. Ho, S.Y. Hsieh and G.H. Chen, Parallel Decomposition of Generalized Series-Parallel Graphs. J. Inform. Sci. Engineer. 15 (1999) 407-417.

[17] M.Y. Kim and J. Song, Multimedia Documents with Elastic Time. Multimedia '95 (1995) 143-154.

[18] J.M. Pla, An Out-of-Kilter Algorithm for Solving Minimum Cost Potential Problems. Math. Programming 1 (1971) 275-290. | MR 303918 | Zbl 0262.90061

[19] R.T. Rockefellar, Convex Analysis. Princeton University Press (1970). | MR 274683 | Zbl 0193.18401

[20] B. Schoenmakers, A New Algorithm for the Recognition of Series Parallel Graphs. Technical report, No CS-59504, Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands (1995).

[21] K. Takamizawa, T. Nishizeki and N. Saito, Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs. J. ACM 29 (1982) 623-641. | MR 666771 | Zbl 0485.68055

[22] J. Valdes, R.E. Tarjan and E.L. Lawler, The Recognition of Series Parallel Digraphs. SIAM J. Comput. 11 (1982) 298-313. | MR 652904 | Zbl 0478.68065