All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 4 Next

Displaying 61 – 80 of 255

Showing per page

Bootstrap clustering for graph partitioning∗

Philippe Gambette, Alain Guénoche (2012)

RAIRO - Operations Research

Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile,...

Bounds of graph parameters for global constraints

Nicolas Beldiceanu, Thierry Petit, Guillaume Rochart (2006)

RAIRO - Operations Research - Recherche Opérationnelle

This article presents a basic scheme for deriving systematically a filtering algorithm from the graph properties based representation of global constraints. This scheme is based on the bounds of the graph parameters used in the description of a global constraint. The article provides bounds for the most common used graph parameters.

Bounds of graph parameters for global constraints

Nicolas Beldiceanu, Thierry Petit, Guillaume Rochart (2007)

RAIRO - Operations Research

This article presents a basic scheme for deriving systematically a filtering algorithm from the graph properties based representation of global constraints. This scheme is based on the bounds of the graph parameters used in the description of a global constraint. The article provides bounds for the most common used graph parameters.

Circuit bases of strongly connected digraphs

Petra M. Gleiss, Josef Leydold, Peter F. Stadler (2003)

Discussiones Mathematicae Graph Theory

The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined.

Clique partitioning of interval graphs with submodular costs on the cliques

Dion Gijswijt, Vincent Jost, Maurice Queyranne (2007)

RAIRO - Operations Research

Given a graph G = (V,E) and a “cost function” f : 2 V → ℝ (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of V(G) 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 G is an interval graph and f belongs to a subclass of submodular set functions, which we call “value-polymatroidal”. This provides a common solution for various generalizations of the...

Colouring graphs with prescribed induced cycle lengths

Bert Randerath, Ingo Schiermeyer (2001)

Discussiones Mathematicae Graph Theory

In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is I ( 4 , 5 ) , the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of I ( 4 , 5 ) are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have...

Comparison of algorithms in graph partitioning

Alain Guénoche (2008)

RAIRO - Operations Research - Recherche Opérationnelle

We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.

Comparison of algorithms in graph partitioning

Alain Guénoche (2009)

RAIRO - Operations Research

We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.

Compositional models, Bayesian models and recursive factorization models

Francesco M. Malvestuto (2016)

Kybernetika

Compositional models are used to construct probability distributions from lower-order probability distributions. On the other hand, Bayesian models are used to represent probability distributions that factorize according to acyclic digraphs. We introduce a class of models, called recursive factorization models, to represent probability distributions that recursively factorize according to sequences of sets of variables, and prove that they have the same representation power as both compositional...

Constrained Steiner trees in Halin graphs

Guangting Chen, Rainer E. Burkard (2003)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

Constrained Steiner trees in Halin graphs

Guangting Chen, Rainer E. Burkard (2010)

RAIRO - Operations Research

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

Currently displaying 61 – 80 of 255