# Minimum convex-cost tension problems on series-parallel graphs

Bruno Bachelet; Philippe Mahey

RAIRO - Operations Research - Recherche Opérationnelle (2003)

- Volume: 37, Issue: 4, page 221-234
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBachelet, Bruno, and Mahey, Philippe. "Minimum convex-cost tension problems on series-parallel graphs." RAIRO - Operations Research - Recherche Opérationnelle 37.4 (2003): 221-234. <http://eudml.org/doc/245319>.

@article{Bachelet2003,

abstract = {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.},

author = {Bachelet, Bruno, Mahey, Philippe},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {minimum cost tension; convex piecewise linear costs; series-parallel graphs},

language = {eng},

number = {4},

pages = {221-234},

publisher = {EDP-Sciences},

title = {Minimum convex-cost tension problems on series-parallel graphs},

url = {http://eudml.org/doc/245319},

volume = {37},

year = {2003},

}

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

PB - EDP-Sciences

VL - 37

IS - 4

SP - 221

EP - 234

AB - 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.

LA - eng

KW - minimum cost tension; convex piecewise linear costs; series-parallel graphs

UR - http://eudml.org/doc/245319

ER -

## References

top- [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. Zbl0948.90116MR1709370
- [2] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows – Theory, Algorithms, and Applications. Prentice Hall (1993). Zbl1201.90001
- [3] J.F. Allen, Maintaining Knowledge about Temporal Intervals. Commun. ACM 26 (1983) 832-843. Zbl0519.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). Zbl0111.17302MR192912
- [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. Zbl0618.68058MR890873
- [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. Zbl1005.68998MR1711638
- [12] R.J. Duffin, Topology of Series-Parallel Networks. J. Math. Anal. Appl. 10 (1965) 303-318. Zbl0128.37002MR175809
- [13] D. Eppstein, Parallel Recognition of Series-Parallel Graphs. Inform. Comput. 98 (1992) 41-55. Zbl0754.68056MR1161075
- [14] D.R. Fulkerson, An Out-of-Kilter Method for Minimal Cost Flow Problems. SIAM J. Appl. Math. 9 (1961) 18-27. Zbl0112.12401
- [15] M. Hadjiat, Penelope’s Graph: a Hard Minimum Cost Tension Instance. Theoret. Comput. Sci. 194 (1998) 207-218. Zbl0912.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. Zbl0262.90061MR303918
- [19] R.T. Rockefellar, Convex Analysis. Princeton University Press (1970). Zbl0193.18401MR274683
- [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. Zbl0485.68055MR666771
- [22] J. Valdes, R.E. Tarjan and E.L. Lawler, The Recognition of Series Parallel Digraphs. SIAM J. Comput. 11 (1982) 298-313. Zbl0478.68065MR652904

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.