|   | 
Details
   web
Records
Author (up) 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 4-regular 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 NP-complete, even if G is a split graph or a bounded-degree 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 polynomial-time algorithms to compute in(cc) (G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter 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 polynomial-time 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 1462-7264 ISBN Medium
Area Expedition Conference
Notes WOS:000431858800001 Approved
Call Number UAI @ eduardo.moreno @ Serial 858
Permanent link to this record
 

 
Author (up) 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 189-200
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 graph-theoretic 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@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-2770 ISBN Medium
Area Expedition Conference
Notes WOS:000354708400003 Approved
Call Number UAI @ eduardo.moreno @ Serial 492
Permanent link to this record
 

 
Author (up) 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 (up) 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 7-9 Pages 1167-1181
Keywords Pursuit-evasion 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 NP-hard 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 NP-hard 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, N-5020 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 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000274886700020 Approved
Call Number UAI @ eduardo.moreno @ Serial 83
Permanent link to this record
 

 
Author (up) 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 (up) Li, B.; Moataz, F.Z.; Nisse, N.; Suchan, K.
Title Minimum size tree-decompositions Type
Year 2018 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 245 Issue Pages 109-127
Keywords Tree-decomposition; Treewidth; NP-hard
Abstract We study in this paper the problem of computing a tree-decomposition 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 tree-decomposition 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 NP-complete 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 2-connected 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 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000435046700011 Approved
Call Number UAI @ eduardo.moreno @ Serial 874
Permanent link to this record
 

 
Author (up) 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 17-27
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 k-chordal graphs, i.e., graphs with no induced cycles of length more than k. In the class of k-chordal 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 n-node 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 k-chordal graphs. We then propose a routing scheme that achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal 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(d-1) 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 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000306041700003 Approved
Call Number UAI @ eduardo.moreno @ Serial 222
Permanent link to this record