Source author record

Benoit Darties

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Networking and Internet Architecture

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Completely Independent Spanning Trees in Some Regular Graphs

Let $k\ge 2$ be an integer and $T_1,\ldots, T_k$ be spanning trees of a graph $G$ . If for any pair of vertices $(u,v)$ of $V(G)$ , the paths from $u$ to $v$ in each $T_i$ , $1\le i\le k$ , do not contain common edges and common vertices, except the vertices $u$ and $v$ , then $T_1,\ldots, T_k$ are completely independent spanning trees in $G$ . For $2k$ -regular graphs which are $2k$ -connected, such as the Cartesian product of a complete graph of order $2k-1$ and a cycle and some Cartesian products of three cycles (for $k=3$ ), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always $k$ .

preprint2010arXiv

A Divide-and-Conquer Scheme for Assigning Roles in Multi-Channel Wireless Mesh Networks

A multi-channel MAC seems to be an interesting approach for improving network throughput by multiplexing transmissions over orthogonal channels. In particular, Molecular MAC has recently proposed to modify the standard IEEE 802.11 DCF access method to use dynamic channel switching for efficient packet forwarding over multiple hops. However, this MAC layer requires role and channel assignment to nodes: some of them use a static channel, while others dynamically switch to neighbor channels on-demand. To assign roles and channels, we extend the notion of the Weakly Connected Dominating Set, the structure already used in clustering. More precisely, we adapt the WCDS structure and introduce new constraints to define what we call a reversible WCDS (r-WCDS), which is particularly suitable for wireless mesh networks operating under Molecular MAC. We propose a divide-and-conquer scheme that partitions the network into clusters with one leader per cluster solving a MILP formulation to assign roles in its cluster. By appropriately defining the roles at the border of clusters, we maintain global connectivity in the r-wcds. Finally, our simulations show that the performance of the propose scheme is close to a centralized algorithm.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.