Browsing by Author "Matamala Vásquez, Martín"
Now showing items 1-14 of 14
-
(ELSEVIER, 1997-06-10)In this paper we consider several notions of alternation in cellular automata: non-uniform, uniform and weak alternation. We study relations among these notions and with alternating Turing machines. It is proved that the ...
-
(Elsevier, 2016)A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p >= 1, all partitions of the vertex set of a bipartite graph into p convex sets ...
-
(2004)Let K be the two-dimensional grid. Let q be an integer greater than 1 and let Q={0; : : : ; q−1}. Let s :Q → Q be de0ned by s( ) = ( + 1) mod q, ∀ ∈ Q. In this work we study the following dynamic F on QZ2 . For x ∈ QZ2 ...
-
(Springer, 2015)An injective coloring of a graph is a vertex labeling such that two vertices sharing a common neighbor get different labels. In this work we introduce and study what we call additive colorings. An injective coloring of a ...
-
(2004)Let be the following strategy to construct a walk in a labeled digraph: at each vertex, we follow the unvisited arc of minimum label. In this work we study for which languages, applying the previous strategy over the ...
-
(SPRINGER-VERLAG BERLIN, 2006)Let G = (V, A) be an Eulerian directed graph with an arc-labeling. In this work we study the problem of finding an Eulerian circuit of lexicographically minimal label among all Eulerian circuits of the graph. We prove that ...
-
(2008)Let G = (V,E) be a graph and T be a spanning tree of G. We consider the following strategy in advancing in G from a vertex x towards a target vertex y: from a current vertex z (initially, z = x), unless z = y, go to a ...
-
(ELSEVIER SCIENCE BV, 2008-04-01)An affine graph is a pair (G, ) where G is a graph and is an automorphism assigning to each vertex of G one of its neighbors. On one hand, we obtain a structural decomposition of any affine graph (G, ) in terms of the ...
-
(ELSEVIER, 2010)In this paper, a strict formulation of a generalization of the classical pickup and delivery problem is presented. Here, we add the flexibility of providing the option for passengers to transfer from one vehicle to another ...
-
(E-JC, 2015)Given a one-factorization F of the complete bipartite graph Kn;n, let pf(F) de- note the number of Hamiltonian cycles obtained by taking pairwise unions of perfect matchings in F. Let pf(n) be the maximum of pf(F) over ...
-
(SIAM PUBLICATIONS, 2012)We consider the problem of coloring a grid using k colors with the restriction that each row and each column has a specific number of cells of each color. This problem has been known as the (k - 1)-atom problem in the ...
-
(JOHN WILEY, 2008-04)A (g, f)-factor of a graph is a subset F of E such that for all v is an element of V, g(v) <= deg(F)(V) <= f(v). Lovasz gave a necessary and sufficient condition for the existence of a (g, f)-factor. We extend, to the case ...
-
(ELSEVIER SCIENCE BV, 2001-04-28)We surveyseveral recent results on cycles of graphs and directed graphs of the following form: ‘Does there exist a set of cycles with a property P that generates all the cycles by operation O?’.
-
(2007-07)Let G be a graph with maximum degree d ≥ 3 and ω(G) ≤ d, where ω(G) is the clique number of the graph G. Let p1 and p2 be two positive integers such that d = p1 + p2. In this work, we prove that G has a vertex ...
