No CrossRef data available.
Article contents
Minimum convex-cost tension problemson series-parallel graphs
Published online by Cambridge University Press: 15 March 2004
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.
Information
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2003
References
Ahuja, R.K., Hochbaum, D.S. and Orlin, J.B., Solving the Convex Cost Integer Dual Network Flow Problem.
Lect. Notes Comput. Sci.
1610 (1999) 31-44.
CrossRef
R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows - Theory, Algorithms, and Applications. Prentice Hall (1993).
Allen, J.F., Maintaining Knowledge about Temporal Intervals.
Commun. ACM
26 (1983) 832-843 .
CrossRef
B. Bachelet, B++ Library. http://frog.isima.fr/bruno/?doc=bpp_library
Bachelet, B. and Mahey, P., Optimisation de la présentation d'un document hypermédia.
Ann. Sci. Univ. Blaise Pascal
110 (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).
Bern, M.W., Lawler, E.L. and Wong, A.L., Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs.
J. Algorithms
8 (1987) 216-235 .
CrossRef
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.
Datta, A.K. and Sen, R.K., Efficient Scheme, An to Solve Two Problems for Two-Terminal Series Parallel Graphs.
Inform. Proc. Lett.
71 (1999) 9-15 .
CrossRef
Duffin, R.J., Topology of Series-Parallel Networks.
J. Math. Anal. Appl.
10 (1965) 303-318 .
CrossRef
Eppstein, D., Parallel Recognition of Series-Parallel Graphs.
Inform. Comput.
98 (1992) 41-55 .
CrossRef
Fulkerson, D.R., Out-of-Kilter Method, An for Minimal Cost Flow Problems.
SIAM J. Appl. Math.
9 (1961) 18-27.
CrossRef
Hadjiat, M., Penelope's Graph: a Hard Minimum Cost Tension Instance.
Theoret. Comput. Sci.
194 (1998) 207-218 .
CrossRef
Ho, C.W., Hsieh, S.Y. and Chen, G.H., 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.
An Out-of-Kilter Al, J.M. Plagorithm for Solving Minimum Cost Potential Problems.
Math. Programming
1 (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).
Takamizawa, K., Nishizeki, T. and Saito, N., Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs.
J. ACM
29 (1982) 623-641 .
CrossRef
Valdes, J., Tarjan, R.E. and Lawler, E.L., The Recognition of Series Parallel Digraphs.
SIAM J. Comput.
11 (1982) 298-313 .
CrossRef
- 7
- Cited by