|   | 
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) de Figueiredo, C.M.H.; Meldanis, J.; de Mello, C.P.; Ortiz, C.
Title Decompositions for the edge colouring of reduced indifference graphs Type
Year 2003 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 297 Issue 1-3 Pages 145-155
Keywords
Abstract The chromatic index problem-finding the minimum number of colours required for colouring the edges of a graph-is still unsolved for indifference graphs, whose vertices can be linearly ordered so that the vertices contained in the same maximal clique are consecutive in this order. We present new positive evidence for the conjecture: every non neighbourhood-overfull indifference graph can be edge coloured with maximum degree colours. Two adjacent vertices are twins if they belong to the same maximal cliques. A graph is reduced if it contains no pair of twin vertices. A graph is overfull if the total number of edges is greater than the product of the maximum degree by [n/2], where n is the number of vertices. We give a structural characterization for neighbourhood-overfull indifference graphs proving that a reduced indifference graph cannot be neighbourhood-overfull. We show that the chromatic index for all reduced indifference graphs is the maximum degree. We present two decomposition methods for edge colouring reduced indifference graphs with maximum degree colours. (C) 2002 Elsevier Science B.V. All rights reserved.
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 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000181732700008 Approved
Call Number UAI @ eduardo.moreno @ Serial 24
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) Gajardo, A.; Goles, E.
Title Crossing information in two-dimensional Sandpiles Type
Year 2006 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 369 Issue 1-3 Pages 463-469
Keywords Sandpile; discrete dynamical system; cellular automata; calculability; complexity
Abstract We prove that in a two-dimensional Sandpile automaton, embedded in a regular infinite planar cellular space, it is impossible to cross information, if the bit of information is the presence (or absence) of an avalanche. This proves that it is impossible to embed arbitrary logical circuits in a Sandpile through quiescent configurations. Our result applies also for the non-planar neighborhood of Moore. Nevertheless, we also show that it is possible to compute logical circuits with a two-dimensional Sandpile, if a neighborhood of radius two is used in Z(2); crossing information becomes possible in that case, and we conclude that for this neighborhood the Sandpde is P-complete and Turing universal. (c) 2006 Elsevier B.V. All rights reserved.
Address Univ Adolfo Ibanez, Santiago, Chile, Email: anahi@ing-mat.udec.cl
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:000242765000035 Approved
Call Number UAI @ eduardo.moreno @ Serial 34
Permanent link to this record
 

 
Author (up) Goles, E.; Guillon, P.; Rapaport, I.
Title Traced communication complexity of cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 30 Pages 3906-3916
Keywords Cellular automata; Communication complexity
Abstract We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata. (C) 2011 Elsevier B.V. All rights reserved.
Address [Guillon, P; Rapaport, I] Univ Chile, DIM CMM, CNRS, UMI 2807, Santiago, Chile, Email: eric.chacc@uai.cl
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:000292589800009 Approved
Call Number UAI @ eduardo.moreno @ Serial 152
Permanent link to this record
 

 
Author (up) Goles, E.; Meunier, P.E.; Rapaport, I.; Theyssier, G.
Title Communication complexity and intrinsic universality in cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 1-2 Pages 2-21
Keywords Cellular automata; Communication complexity; Intrinsic universality
Abstract The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be “universal”, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space-time rescaling and it is intrinsic to the model of cellular automata. intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal. (C) 2010 Elsevier B.V. All rights reserved.
Address [Meunier, P. -E.; Theyssier, G.] Univ Savoie, CNRS, LAMA, F-73376 Le Bourget Du Lac, France, Email: guillaume.theyssier@univ-savoie.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:000285952400002 Approved
Call Number UAI @ eduardo.moreno @ Serial 118
Permanent link to this record
 

 
Author (up) Goles, E.; Montealegre, P.
Title Computational complexity of threshold automata networks under different updating schemes Type
Year 2014 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 559 Issue Pages 3-19
Keywords Automata networks; Threshold functions; Computational complexity; Updating scheme; P-completeness; NC; NP-Hard
Abstract Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND-OR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.
Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias & Tecnol, Santiago, Chile, Email: eric.chacc@uai.cl;
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:000347025300002 Approved
Call Number UAI @ eduardo.moreno @ Serial 434
Permanent link to this record
 

 
Author (up) Goles, E.; Montealegre, P.; Salo, V.; Torma, I.
Title PSPACE-completeness of majority automata networks Type
Year 2016 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 609 Issue Pages 118-128
Keywords Boolean network; Majority network; Prediction problem; PSPACE
Abstract We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the problem of predicting an eventual state change in some vertex, given an initial configuration, is PSPACE-complete. (C) 2015 Elsevier B.V. All rights reserved.
Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl;
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:000367488400009 Approved
Call Number UAI @ eduardo.moreno @ Serial 572
Permanent link to this record
 

 
Author (up) Goles, E.; Montealegre-Barba, P.; Todinca, I.
Title The complexity of the bootstraping percolation and other problems Type
Year 2013 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 504 Issue Pages 73-82
Keywords
Abstract We study the problem of predicting the state of a vertex in automata networks, where the state at each site is given by the majority function over its neighborhood. We show that for networks with maximum degree greater than 5 the problem is P-Complete, simulating a monotone Boolean circuit. Then, we show that the problem for networks with no vertex with degree greater than 4 is in NC, giving a fast parallel algorithm. Finally, we apply the result to the study of related problems. (C) 2012 Elsevier B.V. All rights reserved.
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 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000325905100008 Approved
Call Number UAI @ eduardo.moreno @ Serial 320
Permanent link to this record
 

 
Author (up) Goles, E.; Moreira, A.; Rapaport, I.
Title Communication complexity in number-conserving and monotone cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 29 Pages 3616-3628
Keywords Cellular automata; Communication complexity; Elementary cellular automata; Number-conserving
Abstract One third of the elementary cellular automata (CAs) are either number-conserving (NCCAs) or monotone (increasing or decreasing). In this paper we prove that, for all of them, we can find linear or constant communication protocols for the prediction problem. In other words, we are able to give a succinct description for their dynamics. This is not necessarily true for general NCCAs. In fact, we also show how to explicitly construct, from any CA, a new NCCA which preserves the original communication complexity. (C) 2011 Elsevier B.V. All rights reserved.
Address [Moreira, A] Univ Tecn Federico Santa Maria, Dept Informat, Valparaiso, Chile, Email: eric.chacc@uai.cl
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:000292077200019 Approved
Call Number UAI @ eduardo.moreno @ Serial 153
Permanent link to this record
 

 
Author (up) Goles, E.; Salinas, L.
Title Comparison between parallel and serial dynamics of Boolean networks Type
Year 2008 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 396 Issue 1-3 Pages 247-253
Keywords Boolean network; synchronous update; asynchronous update; attractor; dynamical cycle; fixed point
Abstract In this article we study some aspects about the graph associated with parallel and serial behavior of a Boolean network. We conclude that the structure of the associated graph can give some information about the attractors of the network. We show that the length of the attractors of Boolean networks with a graph by layers is a power of two and under certain conditions the only attractors are fixed points. Also, we show that, under certain conditions, dynamical cycles are not the same for parallel and serial updates of the same Boolean network. (C) 2007 Elsevier B.V. All rights reserved.
Address [Salinas, L.] Univ Chile, Dept Engn Math, Santiago, Chile, Email: eric.chacc@uai.cl
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:000256199100019 Approved
Call Number UAI @ eduardo.moreno @ Serial 32
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
 

 
Author (up) Salinas, L.; Goles, E.
Title Covering by squares Type
Year 2008 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 396 Issue 1-3 Pages 10-27
Keywords discrete geometry; covering; tiling
Abstract In this paper we introduce the “do not touch” condition for squares in the discrete plane. We say that two squares “do not touch” if they do not share any vertex or any segment of an edge. Using this condition we define a covering of the discrete plane, the covering can be strong or weak, regular or non-regular. For simplicity, in this article, we will restrict our attention to regular coverings, i.e., only a size is allowed for the squares and all the squares have the same number of adjacent squares. We establish minimal conditions for the existence of a weak or strong regular covering of the discrete plane, and we give a bound for the number of adjacent squares with respect to the size of the squares in the regular covering. (C) 2007 Elsevier B.V. All rights reserved.
Address [Salinas, L.] Univ Chile, Dept Engn Math, Santiago, Chile, Email: lsalinas@dim.uchile.cl
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:000256199100002 Approved
Call Number UAI @ eduardo.moreno @ Serial 31
Permanent link to this record