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 ...
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
We investigate two different approaches to enumerate minimal dominating sets of a graph using structural properties based on neighborhood inclusion. In the first approach, we define a preference relation on a graph G as a poset on the set of vertices of G. In particular, we consider the poset of closed neighborhood inclusion P(G) and define the not...
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...
Berenbrink, Petra Klasing, Ralf Kosowski, Adrian Mallmann-Trenn, Frederik Uznanski, Przemyslaw
We consider the problem of deterministic load balancing of tokens in the discrete model. A set of $n$ processors is connected into a $d$-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the mo...
Covanov, Svyatoslav Thomé, Emmanuel
For almost 35 years, Schönhage-Strassen's algorithm has been the fastest algorithm known for multiplying integers, with a time complexity O(n · log n · log log n) for multiplying n-bit inputs. In 2007, Fürer proved that there exists K > 1 and an algorithm performing this operation in O(n · log n · K log n). Recent work by Harvey, van der Hoeven, an...