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 operations.
@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}, pages = {221--234}, publisher = {EDP-Sciences}, volume = {37}, number = {4}, year = {2003}, doi = {10.1051/ro:2004202}, mrnumber = {2064599}, zbl = {1101.68715}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro:2004202/} }
TY - JOUR AU - Bachelet, Bruno AU - Mahey, Philippe TI - Minimum convex-cost tension problems on series-parallel graphs JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2003 SP - 221 EP - 234 VL - 37 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2004202/ DO - 10.1051/ro:2004202 LA - en ID - RO_2003__37_4_221_0 ER -
%0 Journal Article %A Bachelet, Bruno %A Mahey, Philippe %T Minimum convex-cost tension problems on series-parallel graphs %J RAIRO - Operations Research - Recherche Opérationnelle %D 2003 %P 221-234 %V 37 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2004202/ %R 10.1051/ro:2004202 %G en %F 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://archive.numdam.org/articles/10.1051/ro:2004202/
[1] Solving the Convex Cost Integer Dual Network Flow Problem. Lect. Notes Comput. Sci. 1610 (1999) 31-44. | MR | Zbl
, and ,[2] Network Flows - Theory, Algorithms, and Applications. Prentice Hall (1993).
, and ,[3] Maintaining Knowledge about Temporal Intervals. Commun. ACM 26 (1983) 832-843. | Zbl
,[4] B++ Library. http://frog.isima.fr/bruno/?doc=bpp_library
,[5] Optimisation de la présentation d'un document hypermédia. Ann. Sci. Univ. Blaise Pascal 110 (2001) 81-90.
and ,[6] Elastic Time Computation for Hypermedia Documents. SBMidìa (2000) 47-62 .
, , and ,[7] Programmes, jeux et réseaux de transport. Dunod (1962). | MR | Zbl
and ,[8] Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs. J. Algorithms 8 (1987) 216-235. | MR | Zbl
, and ,[9] Specifying Temporal Behavior in Hypermedia Documents. Eur. Conference on Hypertext '92 (1992) 262-271.
and ,[10] Automatically Generating Consistent Schedules for Multimedia Documents. Multimedia Systems (1993) 55-67.
and ,[11] An Efficient Scheme to Solve Two Problems for Two-Terminal Series Parallel Graphs. Inform. Proc. Lett. 71 (1999) 9-15. | MR | Zbl
and ,[12] Topology of Series-Parallel Networks. J. Math. Anal. Appl. 10 (1965) 303-318. | MR | Zbl
,[13] Parallel Recognition of Series-Parallel Graphs. Inform. Comput. 98 (1992) 41-55. | MR | Zbl
,[14] An Out-of-Kilter Method for Minimal Cost Flow Problems. SIAM J. Appl. Math. 9 (1961) 18-27. | Zbl
,[15] Penelope's Graph: a Hard Minimum Cost Tension Instance. Theoret. Comput. Sci. 194 (1998) 207-218. | Zbl
,[16] Parallel Decomposition of Generalized Series-Parallel Graphs. J. Inform. Sci. Engineer. 15 (1999) 407-417.
, and ,[17] Multimedia Documents with Elastic Time. Multimedia '95 (1995) 143-154.
and ,[18] An Out-of-Kilter Algorithm for Solving Minimum Cost Potential Problems. Math. Programming 1 (1971) 275-290. | MR | Zbl
,[19] Convex Analysis. Princeton University Press (1970). | MR | Zbl
,[20] 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] Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs. J. ACM 29 (1982) 623-641. | MR | Zbl
, and ,[22] The Recognition of Series Parallel Digraphs. SIAM J. Comput. 11 (1982) 298-313. | MR | Zbl
, and ,Cited by Sources: