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

Abstract

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

How to cite

top

Bachelet, 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
  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.  
  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. ACM26 (1983) 832-843 .  
  4. B. Bachelet, B++ Library.  URIhttp://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 Pascal110 (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).  
  8. M.W. Bern, E.L. Lawler and A.L. Wong, Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs. J. Algorithms8 (1987) 216-235 .  
  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 .  
  12. R.J. Duffin, Topology of Series-Parallel Networks. J. Math. Anal. Appl.10 (1965) 303-318 .  
  13. D. Eppstein, Parallel Recognition of Series-Parallel Graphs. Inform. Comput.98 (1992) 41-55 .  
  14. D.R. Fulkerson, An Out-of-Kilter Method for Minimal Cost Flow Problems. SIAM J. Appl. Math.9 (1961) 18-27.  
  15. M. Hadjiat, Penelope's Graph: a Hard Minimum Cost Tension Instance. Theoret. Comput. Sci.194 (1998) 207-218 .  
  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. Programming1 (1971) 275-290 .  
  19. R.T. Rockefellar, Convex Analysis. Princeton University Press (1970).  
  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. ACM29 (1982) 623-641 .  
  22. J. Valdes, R.E. Tarjan and E.L. Lawler, The Recognition of Series Parallel Digraphs. SIAM J. Comput.11 (1982) 298-313 .  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.