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

Voir la notice de l'article provenant de la source Numdam

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
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},
     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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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. | Zbl | MR

[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). | Zbl | MR

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

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

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

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

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

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

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

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

Cité par Sources :