Zobrazeno 1 - 10
of 436
pro vyhledávání: '"Feuilloley, P."'
Local certification is the area of distributed network computing asking the following question: How to certify to the nodes of a network that a global property holds, if they are limited to a local verification? In this area, it is often essential to
Externí odkaz:
http://arxiv.org/abs/2409.15404
In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results h
Externí odkaz:
http://arxiv.org/abs/2409.01305
This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowl
Externí odkaz:
http://arxiv.org/abs/2408.10757
Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph detection from the perspective of local certification. Remember that a l
Externí odkaz:
http://arxiv.org/abs/2402.12148
In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide if the network satisfies a given property, thanks to small pieces of in
Externí odkaz:
http://arxiv.org/abs/2402.03849
Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. For many classic global properties, like checking the acy
Externí odkaz:
http://arxiv.org/abs/2312.13702
Consider a dynamic network and a given distributed problem. At any point in time, there might exist several solutions that are equally good with respect to the problem specification, but that are different from an algorithmic perspective, because som
Externí odkaz:
http://arxiv.org/abs/2304.05831
A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors. These characterizations play a key role in graph theory, but they rarely lead to efficient algorithms to recognize these classes. In contrast, many
Externí odkaz:
http://arxiv.org/abs/2302.11619
Autor:
Martínez, Virgina Ardévol, Caoduro, Marco, Feuilloley, Laurent, Narboni, Jonathan, Pournajafi, Pegah, Raymond, Jean-Florent
Publikováno v:
Theoretical Computer Science, Volume 971, 2023, 114068
Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct. The quality of a certification is measured by the size of its labels:
Externí odkaz:
http://arxiv.org/abs/2208.14229
Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring $\sigma$ to a target coloring $\eta$. Adding the constraint that each pair of consecutive colorings must differ on exactly one vertex, one asks:
Externí odkaz:
http://arxiv.org/abs/2203.08885