1,721,066 research outputs found
A note on the Cornaz-Jost transformation to solve the graph coloring problem
Full text linkIn this note, we use a reduction by Cornaz and Jost from the graph (max-)coloring problem to the maximum (weighted) stable set problem in order to characterize new graph classes where the graph coloring problem and the more general max-coloring problem can be solved in polynomial time.Fil: Bonomo, Flavia. Consejo Nacional de Invest.cientif.y Tecnicas. Oficina de Coordinacion Administrativa Ciudad Universitaria. Instituto de Investigaciones Matematicas; ArgentinaFil: Giandomenico, Monia. Universita degli Studi dell'Aquila; ItaliaFil: Rossi, Fabrizio. Universita degli Studi dell'Aquila; Itali
On the Minimum Sum Coloring of P4-sparse graphs
Full text linkIn this paper, we study the Minimum Sum Coloring (MSC) problem on P4-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P4-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P4-sparse graphs.Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santalo". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santalo"; ArgentinaFil: Valencia Pabon, Mario. Universite de Paris 13-Nord; Franci
Characterization of classical graph classes by weighted clique graphs
Full text linkGiven integers m1,…,mℓ, the weighted clique graph of G is the clique graph K(G), in which there is a weight assigned to each complete set S of size mi of K(G), for each i=1,…,ℓ. This weight equals the cardinality of the intersection of the cliques of G corresponding to S. We characterize weighted clique graphs in similar terms as Roberts and Spencer’s characterization of clique graphs. Further we characterize several classical graph classes in terms of their weighted clique graphs, providing a common framework for describing some different well-known classes of graphs, as hereditary clique-Helly graphs, split graphs, chordal graphs, interval graphs, proper interval graphs, line graphs, among others.Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santalo". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santalo"; ArgentinaFil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasi
Between coloring and list-coloring: μ-coloring
Full text linkA new variation of the coloring problem, mu-coloring, is defined in this paper. A coloring of a graph G = (V,E) is a function f: V -> N such that f(v) is different from f(w) if v is adjacent to w. Given a graph G = (V,E) and a function mu: V -> N, G is mu-colorable if it admits a coloring f with f(v)<= mu(v) for each v in V. It is proved that mu-coloring lies between coloring and list-coloring, in the sense of generalization of problems and computational complexity. Besides, the notion of perfection is extended to mu-coloring, giving rise to a new characterization of cographs. Finally, a polynomial time algorithm to solve mu-coloring for cographs is shown.Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; ArgentinaFil: Cecowski Palacio, Mariano. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentin
A new approach on locally checkable problems
No full textBy providing a new framework, we extend previous results on locally checkable problems in bounded treewidth graphs. As a consequence, we show how to solve, in polynomial time for bounded treewidth graphs, [k]-Roman domination and Grundy domination, among other problems for which no such algorithm was previously known. Moreover, by proving that fixed powers of bounded degree and bounded treewidth graphs are also bounded degree and bounded treewidth graphs, we can enlarge the family of problems that can be solved in polynomial time for these graph classes, including distance coloring problems and distance domination problems (for bounded distances).Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; ArgentinaFil: González, Carolina Lucía. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentin
Optimality of DSatur algorithm on chordal graphs
No full textDSatur is a widely-used heuristic algorithm for graph coloring, proposed by Daniel Brélaz in 1979. It is based on the greedy coloring approach, but selecting the next vertex to be colored from those that maximize the number of colors already used by their neighbors. Though not always optimal, this algorithm is known to be optimal on certain families, like cycles or bipartite graphs. In this paper, we prove the optimality of DSatur on chordal graphs, a superclass of interval graphs.Fil: Yekezare, N.. Islamic Azad University; IránFil: Zohrehbandian, M.. Islamic Azad University; IránFil: Maghasedi, M.. Islamic Azad University; IránFil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentin
On the L(2,1)-labeling of block graphs
Full text linkThe distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k.Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; ArgentinaFil: Cerioli, Marcia R.. Universidade Federal do Rio de Janeiro; Brasi
Sobre la thinness de árboles
No full textEl concepto de thinness fue introducido por [Man+07]. Grafos con thinness acotada son una generalización de los grafos de intervalo, que son aquellos con thinness 1. Para entender el concepto de thinness de un grafo vamos a imaginar a los nodos del mismo como fichitas de un juego donde cada ficha tendrá un conjunto de fichas vecinas. Sea una ficha f que representa el nodo x en el grafo, las fichas vecinas de f serán los nodos adyacentes a x en el grafo. Para calcular la thinness del grafo, asignaremos a cada fichita un número. Luego iremos armando pilas con las fichas de forma tal que siempre se cumpla que al momento de agregar una ficha nueva a una pila cualquiera, si esta ficha tiene fichas vecinas en alguna pila, todas las fichas que se encuentran por encima de la vecina, también son vecinas. El orden en el que se apilan las fichas está dado por el número asociado a la misma. El valor de la thinness del grafo es la mínima cantidad de pilas posibles, para cualquier orden de las fichas. En esta tesis vamos a calcular la thinness para grafo con un orden prefijado (thin<(G)), es decir, la mínima cantidad de pilas para un orden fijo de las fichas. En grafos de thinness acotada, muchos problemas NP-completos pueden ser resueltos en tiempo polinomial, como por ejemplo el problema del conjunto independiente ponderado máximo [Man+07] o el problema de coloreo capacitado con aplicación al problema de combinación de recorrido de recogida y entrega [BMO11]. Dado un orden para un grafo, la complejidad de hallar la thinness, para ese orden en particular, es O (n a la potencia 3 ) con n la cantidad de nodos del grafo. Esto es así ya que hallar la thinness del grafo es equivalente a encontrar el coloreo en un grafo auxiliar (asociado al orden) también de n vértices pero que resulta de co-comparabilidad [BE18]. Es un problema abierto la complejidad computacional de calcular la thinness de un grafo sin un orden prefijado. En esta tesis se realiza un estudio sobre la thinness para orden fijo en grafos sin ciclos (árboles o bosques). Dado un orden con estructura recursiva para numerar los nodos del árbol (como inorder, preorder, postorder o BFS), calcularemos la thinness en tiempo lineal i en la cantidad de nodos introduciendo el nuevo concepto de Grupos de Conflicto.Fil: Rabinowicz, Lucía. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina
On PVPG graphs: a subclass of vertex intersection graphs of paths on a grid
Full text linkIn this paper, we study the class of PVPG graphs, this is a subclass of VPG graphs such that all the representing paths are between two parallel lines of the grid and have their endpoints on these lines. We prove that PVPG = Co-comparability. Moreover, we present some minimal forbidden induced subgraphs for the class of B1-PVPG graphs.Fil: Alcón, Liliana Graciela. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; ArgentinaFil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Mazzoleni, María Pía. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; ArgentinaFil: de Souza Oliveira, Fabiano. Universidade do Estado de Rio do Janeiro; Brasi
Graph classes with and without powers of bounded clique-width
No full textFil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina.Fil: Grippo, Luciano Norberto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina.Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.Fil: Safe, Martín D. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina.Fil: Milanič, Martin. Universidad de Primorska; Eslovenia.We initiate the study of graph classes of power-bounded clique-width, that is, graph classes
for which there exist integers k and ℓ such that the kth powers of the graphs are of cliquewidth at most ℓ. We give sufficient and necessary conditions for this property. As our
main results, we characterize graph classes of power-bounded clique-width within classes
defined by either one forbidden induced subgraph, or by two connected forbidden induced
subgraphs. We also show that for every positive integer k, there exists a graph class such
that the kth powers of graphs in the class form a class of bounded clique-width, while this
is not the case for any smaller power
- …
