An exact performance bound for an time greedy matching procedure.
An exploration of the permanent-determinant method.
An inequality chain of domination parameters for trees
We prove that the smallest cardinality of a maximal packing in any tree is at most the cardinality of an R-annihilated set. As a corollary to this result we point out that a set of parameters of trees involving packing, perfect neighbourhood, R-annihilated, irredundant and dominating sets is totally ordered. The class of trees for which all these parameters are equal is described and we give an example of a tree in which most of them are distinct.
Approximation algorithms for some graph partitioning problems.
Approximation algorithms for the design of SDH/SONET networks
In this paper, a graph partitioning problem that arises in the design of SONET/SDH networks is defined and formalized. Approximation algorithms with performance guarantees are presented. To solve this problem efficiently in practice, fast greedy algorithms and a tabu-search method are proposed and analyzed by means of an experimental study.
Approximation algorithms for the design of SDH/SONET networks
In this paper, a graph partitioning problem that arises in the design of SONET/SDH networks is defined and formalized. Approximation algorithms with performance guarantees are presented. To solve this problem efficiently in practice, fast greedy algorithms and a tabu-search method are proposed and analyzed by means of an experimental study.
Arbitrarily vertex decomposable caterpillars with four or five leaves
A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ 1,...,k, induces a connected subgraph of G on vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable caterpillars...
Asymptotically optimal tree-packings in regular graphs.
Balanced path decomposition of and
Let denote a path with edges and denote the -fold complete bipartite graph with both parts of size . In this paper, we obtain the necessary and sufficient conditions for to have a balanced -decomposition. We also obtain the directed version of this result.
Bipartite coverings and the chromatic number.
Bipartite toughness and -factors in bipartite graphs.
𝓟-bipartitions of minor hereditary properties
We prove that for any two minor hereditary properties 𝓟₁ and 𝓟₂, such that 𝓟₂ covers 𝓟₁, and for any graph G ∈ 𝓟₂ there is a 𝓟₁-bipartition of G. Some remarks on minimal reducible bounds are also included.
Block-closed subgraphs and q-partitions of graphs
Bootstrap clustering for graph partitioning
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,...
Bootstrap clustering for graph partitioning∗
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 for the Number of Perfect Matchings in Hexagonal Systems
Calculating the number of the linear factors in planar graphs.
Characteristics And Maching Polynomials Of Some Compound Graphs
Characterization of magic graphs
Clique packings and clique partitions of graphs without odd chordless cycles
In this paper we consider partitions (resp. packings) of graphs without odd chordless cycles into cliques of order at least 2. We give a structure theorem, min-max results and characterization theorems for this kind of partitions and packings.