Consider an undirected graph G and a subgraph H of G, on the same vertex set. The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., k}, and moreover for each edge of H, the colours of its ends differ by at least q. In this paper we focus on the case when G is planar and H is a...
-
November 2012 (v1)ReportUploaded on: December 4, 2022
-
2014 (v1)Journal article
Consider an undirected graph $G$ and a subgraph $H$ of $G$, on the same vertex set. The {\it $q$-backbone chromatic number} $\BBC_q(G,H)$ is the minimum $k$ such that $G$ can be properly coloured with colours from $\{1, \dots, k\}$, and moreover for each edge of $H$, the colours of its ends differ by at least $q$. In this paper we focus on the...
Uploaded on: February 28, 2023 -
2011 (v1)Conference paper
Nous étudions quelles propriétés d'un réseau peuvent être calculées à partir d'une petite quantité d'informations locales fournie par ses noeuds. Notre modèle est une restriction de CONGEST, un modèle distribué classique. Il est proche du modèle de complexité de communication avec messages simultanés de Babai et al. Chacun des n noeuds --qui ne...
Uploaded on: December 3, 2022 -
September 2010 (v1)Report
In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and...
Uploaded on: February 22, 2023 -
2011 (v1)Conference paper
In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and...
Uploaded on: December 3, 2022 -
2015 (v1)Journal article
In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graph-theoretic properties, nodes...
Uploaded on: March 25, 2023