
Records 
Links 

Author 
Araujo, J.; Ducoffe, G.; Nisse, N.; Suchan, K. 


Title 
On interval number in cycle convexity 
Type 


Year 
2018 
Publication 
Discrete Mathematics And Theoretical Computer Science 
Abbreviated Journal 
Discret. Math. Theor. Comput. Sci. 


Volume 
20 
Issue 
1 
Pages 
35 pp 


Keywords 
graph convexity; interval number; domination problems in graphs; complexity and algorithms 


Abstract 
Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by in(cc)(G), is the minimum cardinality of a set S subset of V (G) such that every vertex w is an element of E V (G) \ S has two distinct neighbors u, v is an element of S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S. In this work, first we provide bounds on in(cc) (G) and its relations to other graph convexity parameters, and explore its behaviour on grids. Then, we present some hardness results by showing that deciding whetherin(cc) (G) <= k is NPcomplete, even if G is a split graph or a boundeddegree planar graph, and that the problem is W[2]hard in bipartite graphs when k is the parameter. As a consequence, we obtain that in(cc) (G) cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = NP). On the positive side, we present polynomialtime algorithms to compute in(cc) (G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixedparameter tractable (FPT) algorithms to compute it for (q, q – 4)graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G. Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomialtime algorithms can be helpful in order to advance in the study of related graph problems. 


Address 
[Araujo, Julio] Univ Fed Ceara, Dept Matemat, ParGO, Fortaleza, Ceara, Brazil 


Corporate Author 

Thesis 



Publisher 
Discrete Mathematics Theoretical Computer Science 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
14627264 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000431858800001 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
858 

Permanent link to this record 




Author 
Becker, F.; Kosowski, A.; Matamala, M.; Nisse, N.; Rapaport, I.; Suchan, K.; Todinca, I. 


Title 
Allowing each node to communicate only once in a distributed system: shared whiteboard models 
Type 


Year 
2015 
Publication 
Distributed Computing 
Abbreviated Journal 
Distrib. Comput. 


Volume 
28 
Issue 
3 
Pages 
189200 


Keywords 
Distributed computing; Local computation; Graph properties; Bounded communication 


Abstract 
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 graphtheoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model. 


Address 
[Becker, Florent; Todinca, Ioan] Univ Orleans, LIFO, Orleans, France, Email: florent.becker@univorleans.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 
01782770 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000354708400003 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
492 

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 
10551096 


Keywords 
Distributed computing; Exploration; Searching; Gathering; Oblivious anonymous robots; Asynchronous anonymous networks; LookComputeMove 


Abstract 
A set of autonomous robots have to collaborate in order to accomplish a common task in a ringtopology 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 LookComputeMove 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 ringtopologies. 


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 
01784617 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000356461400008 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
504 

Permanent link to this record 




Author 
Fomin, F.V.; Golovach, P.A.; Kratochvil, J.; Nisse, N.; Suchan, K. 


Title 
Pursuing a fast robber on a graph 
Type 


Year 
2010 
Publication 
Theoretical Computer Science 
Abbreviated Journal 
Theor. Comput. Sci. 


Volume 
411 
Issue 
79 
Pages 
11671181 


Keywords 
Pursuitevasion game on graphs; Cops and Robbers; Complexity; Parameterized complexity; Cliquewidth; Planar graph 


Abstract 
The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been Much Studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NPhard and that the parameterized version of the problem is W[2]hard; the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s = 1 but is NPhard if s = 2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s <= 2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. (C) 2009 Elsevier B.V. All rights reserved. 


Address 
[Fomin, Fedor V.; Golovach, Petr A.] Univ Bergen, Dept Informat, N5020 Bergen, Norway, Email: petr.golovach@durham.ac.uk 


Corporate Author 

Thesis 



Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
03043975 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000274886700020 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
83 

Permanent link to this record 




Author 
Gaspers, S.; Liedloff, M.; Stein, M.; Suchan, K. 


Title 
Complexity of splits reconstruction for lowdegree trees 
Type 


Year 
2015 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 


Volume 
180 
Issue 

Pages 
89100 


Keywords 
Reconstruction of trees; Computational complexity; Computational chemistry 


Abstract 
Given a vertexweighted tree T, the split of an edge em T is the minimum over the weights of the two trees obtained by removing e from T, where the weight of a tree is the sum of weights of its vertices. Given a set of weighted vertices V and a multiset of integers s, we consider the problem of constructing a tree on V whose splits correspond to s. The problem is known to be NPcomplete, even when all vertices have unit weight and the maximum vertex degree of T is required to be at most 4. We show that the problem is strongly NPcomplete when T is required to be a path, the problem is NPcomplete when all vertices have unit weight and the maximum degree of T is required to be at most 3, and it remains NPcomplete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3. We also design polynomial time algorithms for the variant where T is required to be a path and the number of distinct vertex weights is constant, and the variant where all vertices have unit weight and T has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but also is a fixedparameter algorithm for parameter k. Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm. The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong relation between structural invariants of the particles, such as the Wiener index and, less directly, the problem under consideration here, and physicochemical properties of the substance. (C) 2014 Elsevier B.V. All rights reserved. 


Address 
[Gaspers, Serge] Univ New S Wales, Sch Comp Sci & Engn, Sydney, NSW 2052, Australia, Email: sergeg@cse.unsw.edu.au; 


Corporate Author 

Thesis 



Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
0166218x 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000346545500009 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
433 

Permanent link to this record 




Author 
Kosowski, A.; Li, B.; Nisse, N.; Suchan, K. 


Title 
kChordal Graphs: From Cops and Robber to Compact Routing via Treewidth 
Type 


Year 
2015 
Publication 
Algorithmica 
Abbreviated Journal 
Algorithmica 


Volume 
72 
Issue 
3 
Pages 
758777 


Keywords 
Treewidth; Chordality; Compact routing; Cops and robber games 


Abstract 
Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(23), 235239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 8992, 1985), concern a team of cops that must capture a robber moving in a graph. We consider the class of kchordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, ka parts per thousand yen3. We prove that k1 cops are always sufficient to capture a robber in kchordal graphs. This leads us to our main result, a new structural decomposition for a graph class including kchordal graphs. We present a polynomialtime 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 treedecomposition of G, each bag of which contains a dominating path with at most k1 vertices. This allows us to prove that any kchordal graph with maximum degree Delta has treewidth at most (k1)(Delta1)+2, improving the O(Delta(Delta1) (k3)) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(13), 4561, 1997. Moreover, any graph admitting such a treedecomposition has small hyperbolicity). As an application, for any nvertex graph admitting such a treedecomposition, 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 kchordal 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 
01784617 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000355939800004 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
503 

Permanent link to this record 




Author 
Kowalik, L.; Pilipczuk, M.; Suchan, K. 


Title 
Towards optimal kernel for connected vertex cover in planar graphs 
Type 


Year 
2013 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 


Volume 
161 
Issue 
78 
Pages 
11541161 


Keywords 
Kernelization; Planar graphs; Connected vertex cover 


Abstract 
We study the parameterized complexity of the connected version of the vertex cover problem, where the solution set has to induce a connected subgraph. Although this problem does not admit a polynomial kernel for general graphs (unless NP subset of coNP/poly), for planar graphs Guo and Niedermeier [ICALP'08] showed a kernel with at most 14k vertices, subsequently improved by Wang et al. [MFCS'11] to 4k. The constant 4 here is so small that a natural question arises: could it be already an optimal value for this problem? In this paper we answer this question in the negative: we show a 11/3 kvertex kernel for CONNECTED VERTEX COVER in planar graphs. We believe that this result will motivate further study in the search for an optimal kernel. In our analysis, we show an extension of a theorem of Nishizeki and Baybars [Takao Nishizeki, Ilker Baybars, Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Mathematics 28 (3) (1979) 255267] which might be of independent interest: every planar graph with n(>= 3) vertices of degree at least 3 contains a matching of cardinality at least n(>= 3)/3. (C) 2012 Elsevier B.V. All rights reserved. 


Address 
Univ Warsaw, Inst Informat, PL00325 Warsaw, Poland, Email: kowalik@mimuw.edu.pl; 


Corporate Author 

Thesis 



Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
0166218x 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000317451700030 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
276 

Permanent link to this record 




Author 
Lespay, H.; Suchan, K. 


Title 
A case study of consistent vehicle routing problem with time windows 
Type 


Year 
2021 
Publication 
International Transactions In Operational Research 
Abbreviated Journal 
Int. Trans. Oper. Res. 


Volume 
Early Access 
Issue 

Pages 
29 pp 


Keywords 
vehicle routing; multiperiod routing; distribution logistics; service consistency; customer satisfaction; heuristics 


Abstract 
We develop a heuristic for the consistent vehicle routing problem with time windows (ConVRPTW), which is motivated by a realworld application at a food company's distribution center. Besides standard VRPTW restrictions, ConVRPTW assigns each customer just one driver to fulfill his or her orders during the whole multiperiod planning horizon. For each driver and period, a route is sought to serve all their customers with positive demand. For each customer, the number of periods between consecutive orders and the ordered quantities is highly irregular. This causes difficulties in the daily routing, negatively impacting the service level of the company. Similar problems have been studied as ConVRP, where the number of drivers is fixeda priori, and only the total travel time is minimized. Moreover, the clients present no time window constraints, but the visits should be scheduled with a small arrival time variation. In our model, the objective is to minimize the number of drivers. We impose hard time windows but do not consider time consistency in more detail. We compare solutions given by the heuristic with solutions of a mixedinteger linear programming model on a set of small artificial instances and solutions used by the food company on realworld instances. The results show the effectiveness of the heuristic. For the company, we obtain significant improvements in the routing plans, with a lower number of vehicles and a higher rate of orders delivered within the prescribed time window. 


Address 
[Lespay, Hernan] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Ave Diagonal Torres 2640, Santiago 7941169, Chile, Email: hlespay@alumnos.uai.cl; 


Corporate Author 

Thesis 



Publisher 
Wiley 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
09696016 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000579246000001 
Approved 



Call Number 
UAI @ alexi.delcanto @ 
Serial 
1232 

Permanent link to this record 




Author 
Li, B.; Moataz, F.Z.; Nisse, N.; Suchan, K. 


Title 
Minimum size treedecompositions 
Type 


Year 
2018 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 


Volume 
245 
Issue 

Pages 
109127 


Keywords 
Treedecomposition; Treewidth; NPhard 


Abstract 
We study in this paper the problem of computing a treedecomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed k >= 1, what is the complexity of computing a treedecomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NPcomplete for any fixed k >= 4 and polynomial for k <= 2; for k = 3, we show that it is polynomial in the class of trees and 2connected outerplanar graphs. (C) 2017 Elsevier B.V. All rights reserved. 


Address 
[Moataz, Fatima Zahra; Nisse, Nicolas] INRIA, Rennes, France, Email: nicolas.nisse@inria.fr 


Corporate Author 

Thesis 



Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
0166218x 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000435046700011 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
874 

Permanent link to this record 




Author 
Nisse, N.; Rapaport, I.; Suchan, K. 


Title 
Distributed computing of efficient routing schemes in generalized chordal graphs 
Type 


Year 
2012 
Publication 
Theoretical Computer Science 
Abbreviated Journal 
Theor. Comput. Sci. 


Volume 
444 
Issue 

Pages 
1727 


Keywords 
Routing scheme; Stretch; Chordal graph; Distributed algorithm 


Abstract 
Efficient algorithms for computing routing tables should take advantage of particular properties arising in large scale networks. Two of them are of special interest: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose here a routing scheme that computes short routes in the class of kchordal graphs, i.e., graphs with no induced cycles of length more than k. In the class of kchordal graphs, our routing scheme achieves an additive stretch of at most k – 1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k – 1. In order to compute the routing tables of any nnode graph with diameter D we propose a distributed algorithm which uses O(log n)bit messages and takes O(D) time. The corresponding routing scheme achieves the stretch of k – 1 on kchordal graphs. We then propose a routing scheme that achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3chordal graphs). In this case, distributed computation of routing tables takes O(min{Delta D, n}) time, where Delta is the maximum degree of the graph. Our routing schemes use addresses of size log n bits and local memory of size 2(d1) log n bits per node of degree d. (c) 2012 Elsevier B.V. All rights reserved. 


Address 
[Suchan, Karol] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: nicolas.nisse@inria.fr; 


Corporate Author 

Thesis 



Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
03043975 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000306041700003 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
222 

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 
1634 


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 
01784617 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000286525300003 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
119 

Permanent link to this record 