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

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

How to cite

top

Bachelet, 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. [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. [2] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows – Theory, Algorithms, and Applications. Prentice Hall (1993). Zbl1201.90001
  3. [3] J.F. Allen, Maintaining Knowledge about Temporal Intervals. Commun. ACM 26 (1983) 832-843. Zbl0519.68079
  4. [4] B. Bachelet, B++ Library. http://frog.isima.fr/bruno/?doc=bpp_library 
  5. [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. [6] B. Bachelet, P. Mahey, R. Rodrigues and L.F. Soares, Elastic Time Computation for Hypermedia Documents. SBMidìa (2000) 47-62 . 
  7. [7] C. Berge and A. Ghoula-Houri, Programmes, jeux et réseaux de transport. Dunod (1962). Zbl0111.17302MR192912
  8. [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. [9] M.C. Buchanan and P.T. Zellweger, Specifying Temporal Behavior in Hypermedia Documents. Eur. Conference on Hypertext ’92 (1992) 262-271. 
  10. [10] M.C. Buchanan and P.T. Zellweger, Automatically Generating Consistent Schedules for Multimedia Documents. Multimedia Systems (1993) 55-67. 
  11. [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. [12] R.J. Duffin, Topology of Series-Parallel Networks. J. Math. Anal. Appl. 10 (1965) 303-318. Zbl0128.37002MR175809
  13. [13] D. Eppstein, Parallel Recognition of Series-Parallel Graphs. Inform. Comput. 98 (1992) 41-55. Zbl0754.68056MR1161075
  14. [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. [15] M. Hadjiat, Penelope’s Graph: a Hard Minimum Cost Tension Instance. Theoret. Comput. Sci. 194 (1998) 207-218. Zbl0912.68007
  16. [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. [17] M.Y. Kim and J. Song, Multimedia Documents with Elastic Time. Multimedia ’95 (1995) 143-154. 
  18. [18] J.M. Pla, An Out-of-Kilter Algorithm for Solving Minimum Cost Potential Problems. Math. Programming 1 (1971) 275-290. Zbl0262.90061MR303918
  19. [19] R.T. Rockefellar, Convex Analysis. Princeton University Press (1970). Zbl0193.18401MR274683
  20. [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. [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. [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 ?

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.