| Records |
| Author |
Feuilloley, L.; Fraigniaud, P.; Montealegre, P.; Rapaport, I.; Remila, E.; Todinca, I. |
| Title |
Compact Distributed Certification of Planar Graphs |
Type |
|
| Year |
2021 |
Publication |
Algorithmica |
Abbreviated Journal |
Algorithmica |
| Volume |
83 |
Issue |
7 |
Pages  |
2215-2244 |
| Keywords |
Distributed algorithms; Network algorithms; Graph property certification; Labeling schemes; Planarity |
| Abstract |
Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), pp 1096-115, 2020. https://doi.org/10.1137/1.9781611975994.67) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(log n) bits in n-node networks. We show that a single interaction with the prover suffices, and randomization is unecessary, by providing an explicit description of a proof-labeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no proof-labeling schemes-in fact, even no locally checkable proofs-for planarity using certificates on o(log n) bits. |
| Address |
|
| Corporate Author |
|
Thesis |
|
| Publisher |
|
Place of Publication |
|
Editor |
|
| Language |
|
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0178-4617 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000648028200001 |
Approved |
|
| Call Number |
UAI @ alexi.delcanto @ |
Serial |
1376 |
| Permanent link to this record |
| |
|
| |
| Author |
D'Angelo, G.; Di Stefano, G.; Navarra, A.; Nisse, N.; Suchan, K. |
| Title |
Computing on Rings by Oblivious Robots: A Unified Approach for Different Tasks |
Type |
|
| Year |
2015 |
Publication |
Algorithmica |
Abbreviated Journal |
Algorithmica |
| Volume |
72 |
Issue |
4 |
Pages |
1055-1096 |
| Keywords |
Distributed computing; Exploration; Searching; Gathering; Oblivious anonymous robots; Asynchronous anonymous networks; Look-Compute-Move |
| Abstract |
A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often while avoiding that two robots occupy a same node (exclusivity property); in exclusive perpetual clearing (also known as graph searching), the team of robots aims at clearing the whole ring infinitely often (an edge is cleared if it is traversed by a robot or if both its endpoints are occupied); and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the Look-Compute-Move model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in asynchronous cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move). Moreover, robots are endowed with very weak capabilities. Namely, they are anonymous, asynchronous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive and rigid (i.e. aperiodic and asymmetric) configuration, solve the three above problems in anonymous ring-topologies. |
| Address |
[D'Angelo, Gianlorenzo] Gran Sasso Sci Inst GSSI, Laquila, Italy, Email: gianlorenzo.dangelo@gssi.infn.it; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Springer |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0178-4617 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000356461400008 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
504 |
| Permanent link to this record |
| |
|
| |
| Author |
Liedloff, M.; Montealegre, P.; Todinca, I. |
| Title |
Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques |
Type |
|
| Year |
2019 |
Publication |
Algorithmica |
Abbreviated Journal |
Algorithmica |
| Volume |
81 |
Issue |
3 |
Pages |
986-1005 |
| Keywords |
FPT algorithms; Treewidth; Potential maximal cliques |
| Abstract |
Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentH-Packing, etc. Fomin et al. (SIAM J Comput 44(1):54-87, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input. |
| Address |
[Liedloff, Mathieu; Todinca, Ioan] Univ Orleans, INSA Ctr Val Loire, LIFO, EA 4022, Orleans, France, Email: mathieu.liedloff@univ-orleans.fr; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Springer |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0178-4617 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000460105700003 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
989 |
| Permanent link to this record |
| |
|
| |
| Author |
Kosowski, A.; Li, B.; Nisse, N.; Suchan, K. |
| Title |
k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth |
Type |
|
| Year |
2015 |
Publication |
Algorithmica |
Abbreviated Journal |
Algorithmica |
| Volume |
72 |
Issue |
3 |
Pages |
758-777 |
| Keywords |
Treewidth; Chordality; Compact routing; Cops and robber games |
| Abstract |
Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(2-3), 235-239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 89-92, 1985), concern a team of cops that must capture a robber moving in a graph. We consider the class of k-chordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, ka parts per thousand yen3. We prove that k-1 cops are always sufficient to capture a robber in k-chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including k-chordal graphs. We present a polynomial-time algorithm that, given a graph G and ka parts per thousand yen3, either returns an induced cycle larger than k in G, or computes a tree-decomposition of G, each bag of which contains a dominating path with at most k-1 vertices. This allows us to prove that any k-chordal graph with maximum degree Delta has treewidth at most (k-1)(Delta-1)+2, improving the O(Delta(Delta-1) (k-3)) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(1-3), 45-61, 1997. Moreover, any graph admitting such a tree-decomposition has small hyperbolicity). As an application, for any n-vertex graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(klog Delta+logn) bits and achieving an additive stretch of O(klog Delta). As far as we know, this is the first routing scheme with O(klog Delta+logn)-routing tables and small additive stretch for k-chordal graphs. |
| Address |
[Kosowski, A.] INRIA, LaBRI, CEPAGE, Talence, France, Email: bi.li@inria.fr |
| Corporate Author |
|
Thesis |
|
| Publisher |
Springer |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0178-4617 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000355939800004 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
503 |
| Permanent link to this record |
| |
|
| |
| Author |
Rapaport, I.; Suchan, K.; Todinca, I.; Verstraete, J. |
| Title |
On Dissemination Thresholds in Regular and Irregular Graph Classes |
Type |
|
| Year |
2011 |
Publication |
Algorithmica |
Abbreviated Journal |
Algorithmica |
| Volume |
59 |
Issue |
1 |
Pages |
16-34 |
| Keywords |
Bootstrap percolation; Cubic graphs; Information dissemination |
| Abstract |
We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if p < 1/2. We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p. |
| Address |
[Todinca, I.] Univ Orleans, LIFO, Orleans, France, Email: rapaport@dim.uchile.cl |
| Corporate Author |
|
Thesis |
|
| Publisher |
Springer |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0178-4617 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000286525300003 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
119 |
| Permanent link to this record |
