Chepoi, Victor
Published in
Combinatorica
We give a characterization of distance-preserving subgraphs of Johnson graphs, i.e., of graphs which are isometrically embeddable into Johnson graphs (the Johnson graph J(m,∧) has the subsets of cardinality m of a set ∧ as the vertex-set and two such sets A,B are adjacent iff |AΔB|=2). Our characterization is similar to the characterization of D. Ž...
Dufossé, Fanny Kaya, Kamer Panagiotas, Ioannis Uçar, Bora
We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.
Dao, Vinh-Loc Bothorel, Cécile Lenca, Philippe
Published in
Social Network Analysis and Mining
Community detection emerges as an important task in the discovery of network mesoscopic structures. However, the concept of a “good” community is very context-dependent, and it is relatively complicated to deduce community characteristics using available community detection techniques. In reality, the existence of a gap between structural goodness ...
Cohen-Addad, Vincent Colin de Verdière, Éric de Mesmay, Arnaud
International audience
Dorbec, Paul González, Antonio Pennarun, Claire
Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measurement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially...
Defrain, Oscar Nourine, Lhouari
In [M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal on Discrete Mathematics, 28(4):1916–1929, 2014.] the authors give an O(n+m) delay algorithm based on neighborhood inclusions for the enumeration of minimal dominating sets in split and P_6-free chordal graphs. In thi...
Weller, Mathias
Different sources of information might tell different stories about the evolutionary history of a given set of species. This leads to (rooted) phylogenetic trees that " disagree " on triples of species, which we call " conflict triples ". An important subtask of computing consensus trees which is interesting in its own regard is the enumeration of ...
Cazaux, Bastien Lecroq, Thierry Rivals, Eric
DNA sequencing technologies have tremendously increased their throughput, and hence complicated DNA assembly. Numerous assembly programs use de Bruijn graphs (dBG) built from short reads to merge these into contigs, which represent putative DNA segments. In a dBG of order k, nodes are substrings of length k of reads (or k-mers), while arcs are thei...
azaïs, romain
Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by directed acrylic graph (DAG) compression. A method for quantifying the degree of self-similarity of plants through self-nested trees was introduced by Godin and Ferraro in 2010. The procedure consists of computing a self-nested ...
Gupta, Siddharth Kosowski, Adrian Viennot, Laurent
For fixed $h \geq 2$, we consider the task of adding to a graph $G$ a set of weighted shortcut edges on the same vertex set, such that the length of a shortest $h$-hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in $G$. A set of shortcut edges with this property is cal...