Displaying similar documents to “Minimum convex-cost tension problems on series-parallel graphs”

Control flow graphs and code coverage

Robert Gold (2010)

International Journal of Applied Mathematics and Computer Science

Similarity:

The control flow of programs can be represented by directed graphs. In this paper we provide a uniform and detailed formal basis for control flow graphs combining known definitions and results with new aspects. Two graph reductions are defined using only syntactical information about the graphs, but no semantical information about the represented programs. We prove some properties of reduced graphs and also about the paths in reduced graphs. Based on graphs, we define statement coverage...

Clique partitioning of interval graphs with submodular costs on the cliques

Dion Gijswijt, Vincent Jost, Maurice Queyranne (2007)

RAIRO - Operations Research

Similarity:

Given a graph and a “cost function” f : 2 V → ℝ (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of of minimum cost. Here, the cost of a partition is the sum of the costs of the cliques in the partition. We provide a polynomial time dynamic program for the case where is an interval graph and belongs to a subclass of submodular set functions, which we call “value-polymatroidal”. This provides a common solution for various generalizations of the coloring problem...

A polynomial algorithm for minDSC on a subclass of series Parallel graphs

Salim Achouri, Timothée Bossart, Alix Munier-Kordon (2009)

RAIRO - Operations Research

Similarity:

The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.