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

Bruno Bachelet; Philippe Mahey

RAIRO - Operations Research (2010)

- 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 37.4 (2010): 221-234. <http://eudml.org/doc/105292>.

@article{Bachelet2010,

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(m3) operations.
},

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

journal = {RAIRO - Operations Research},

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

language = {eng},

month = {3},

number = {4},

pages = {221-234},

publisher = {EDP Sciences},

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

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

volume = {37},

year = {2010},

}

TY - JOUR

AU - Bachelet, Bruno

AU - Mahey, Philippe

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

JO - RAIRO - Operations Research

DA - 2010/3//

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(m3) operations.

LA - eng

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

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

ER -

## References

top- 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.
- R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows - Theory, Algorithms, and Applications. Prentice Hall (1993).
- J.F. Allen, Maintaining Knowledge about Temporal Intervals. Commun. ACM26 (1983) 832-843 .
- B. Bachelet, B++ Library. URIhttp://frog.isima.fr/bruno/?doc=bpp_library
- B. Bachelet and P. Mahey, Optimisation de la présentation d'un document hypermédia. Ann. Sci. Univ. Blaise Pascal110 (2001) 81-90.
- B. Bachelet, P. Mahey, R. Rodrigues and L.F. Soares, Elastic Time Computation for Hypermedia Documents. SBMidìa (2000) 47-62 .
- C. Berge and A. Ghoula-Houri, Programmes, jeux et réseaux de transport. Dunod (1962).
- M.W. Bern, E.L. Lawler and A.L. Wong, Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs. J. Algorithms8 (1987) 216-235 .
- M.C. Buchanan and P.T. Zellweger, Specifying Temporal Behavior in Hypermedia Documents. Eur. Conference on Hypertext '92 (1992) 262-271.
- M.C. Buchanan and P.T. Zellweger, Automatically Generating Consistent Schedules for Multimedia Documents. Multimedia Systems (1993) 55-67.
- 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 .
- R.J. Duffin, Topology of Series-Parallel Networks. J. Math. Anal. Appl.10 (1965) 303-318 .
- D. Eppstein, Parallel Recognition of Series-Parallel Graphs. Inform. Comput.98 (1992) 41-55 .
- D.R. Fulkerson, An Out-of-Kilter Method for Minimal Cost Flow Problems. SIAM J. Appl. Math.9 (1961) 18-27.
- M. Hadjiat, Penelope's Graph: a Hard Minimum Cost Tension Instance. Theoret. Comput. Sci.194 (1998) 207-218 .
- 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.
- M.Y. Kim and J. Song, Multimedia Documents with Elastic Time. Multimedia '95 (1995) 143-154.
- J.M. Pla, An Out-of-Kilter Algorithm for Solving Minimum Cost Potential Problems. Math. Programming1 (1971) 275-290 .
- R.T. Rockefellar, Convex Analysis. Princeton University Press (1970).
- 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).
- K. Takamizawa, T. Nishizeki and N. Saito, Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs. J. ACM29 (1982) 623-641 .
- J. Valdes, R.E. Tarjan and E.L. Lawler, The Recognition of Series Parallel Digraphs. SIAM J. Comput.11 (1982) 298-313 .

## NotesEmbed ?

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