Minimum convex-cost tension problems on series-parallel graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 4, pp. 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(m 3 ) operations.

DOI : 10.1051/ro:2004202
Mots-clés : 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},
     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://www.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://www.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://www.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, Tome 37 (2003) no. 4, pp. 221-234. doi : 10.1051/ro:2004202. http://www.numdam.org/articles/10.1051/ro:2004202/

[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 | Zbl

[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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

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

[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 | Zbl

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

[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 | Zbl

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

Cité par Sources :