The search session has expired. Please query the service again.
Displaying 61 –
80 of
255
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,...
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.
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.
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.
Given a graph G = (V,E) and a “cost function” (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...
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 , the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have...
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.
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 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...
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.
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