Minimum convex piecewise linear cost tension problem on quasi-<Emphasis Type="Italic">k</Emphasis> series-parallel graphs |
| |
Authors: | Email author" target="_blank">Bruno?BacheletEmail author Philippe?Mahey |
| |
Institution: | (1) LIMOS, UMR 6158-CNRS, Université Blaise-Pascal, BP 10125, 63173 Aubière, France |
| |
Abstract: | Some hypermedia synchronization issues request the resolution of the minimum convex piecewise linear cost tension problem (CPLCT problem) on directed graphs that are close to two-terminal series-parallel graphs (TTSP-graphs), the so-called quasi-k series-parallel graphs (k-QSP graphs). An aggregation algorithm has already been introduced for the CPLCT problem on TTSP-graphs. We propose here a reconstruction method, based on the aggregation and the well-known out-of-kilter techniques, to solve the problem on k-QSP graphs. One of the main steps being to decompose a graph into TTSP-subgraphs, methods based on the recognition of TTSP-graphs are thoroughly discussed.Received: October 2003, Revised: July 2004, MSC classification:
90C35, 05C85 |
| |
Keywords: | Minimum cost tension two-terminal series-parallel digraph graph decomposition series-parallel recognition out-of-kilter algorithm |
本文献已被 SpringerLink 等数据库收录! |
|