Title | ||
---|---|---|
Minimum convex piecewise linear cost tension problem on quasi-k series-parallel graphs. |
Abstract | ||
---|---|---|
Abstract This article proposes an extension, combined with the out-of-kilter technique, of the aggregation method (that solves the minimum convex piecewise linear cost tension problem, or CPLCT, on series-parallel graphs) to solve CPLCT on quasi series-parallel graphs. To make,this algorithm efficient, the key point is to find a "good" way of decomposing t he graph into series-parallel subgraphs. Decomposition techniques, based on the recognition of series-parallel graphs, are thoroughly discussed. Keywords: minimum cost tension, series-parallel graph, graph decomposition, series-parallel |
Year | DOI | Venue |
---|---|---|
2004 | 10.1007/s10288-004-0049-3 | 4OR |
Keywords | Field | DocType |
series parallel,piecewise linear | Discrete mathematics,Mathematical optimization,Modular decomposition,Combinatorics,Indifference graph,Series-parallel graph,Chordal graph,Cograph,Pathwidth,Longest path problem,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
2 | 4 | 1614-2411 |
Citations | PageRank | References |
4 | 0.48 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bruno Bachelet | 1 | 30 | 5.74 |
Philippe Mahey | 2 | 174 | 20.95 |