Source author record

Graciela Nasini

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2018arXiv

A Branch and Price Algorithm for List Coloring Problem

Coloring problems in graphs have been used to model a wide range of real applications. In particular, the List Coloring Problem generalizes the well-known Graph Coloring Problem for which many exact algorithms have been developed. In this work, we present a Branch-and-Price algorithm for the weighted version of the List Coloring Problem, based on the one developed by Mehrotra and Trick (1996) for the Graph Coloring Problem. This version considers non-negative weights associated to each color and it is required to assign a color to each vertex from predetermined lists in such a way the sum of weights of the assigned colors is minimum. Computational experiments show the good performance of our approach, being able to comfortably solve instances whose graphs have up to seventy vertices. These experiences also bring out that the hardness of the instances of the List Coloring Problem does not seem to depend only on quantitative parameters such as the size of the graph, its density, and the size of list of colors, but also on the distribution of colors present in the lists.

preprint2016arXiv

Total dominating sequences in trees, split graphs, and under modular decomposition

A sequence of vertices in a graph $G$ with no isolated vertices is called a total dominating sequence if every vertex in the sequence totally dominates at least one vertex that was not totally dominated by preceding vertices in the sequence, and, at the end all vertices of $G$ are totally dominated (by definition a vertex totally dominates its neighbors). The maximum length of a total dominating sequence is called the Grundy total domination number, $γ_{\rm gr}^t(G)$ , of $G$ , as introduced in [B. Brešar, M.A. Henning, and D. F. Rall, Total dominating sequences in graphs, Discrete Math. 339 (2016), 1165--1676]. In this paper we continue the investigation of this concept, mainly from the algorithmic point of view. While it was known that the decision version of the problem is NP-complete in bipartite graphs, we show that this is also true if we restrict to split graphs. A linear time algorithm for determining the Grundy total domination number of an arbitrary tree $T$ is presented, based on the formula $γ_{\rm gr}^t(T)=2τ(T)$ , where $τ(T)$ is the vertex cover number of $T$ . A similar efficient algorithm is presented for bipartite distance-hereditary graphs. Using the modular decomposition of a graph, we present a frame for obtaining polynomial algorithms for this problem in classes of graphs having relatively simple modular subgraphs. In particular, a linear algorithm for determining the Grundy total domination number of $P_4$ -tidy graphs is presented. In addition, we prove a realization result by exhibiting a family of graphs $G_k$ such that $γ_{\rm gr}^t(G_k)=k$ , for any $k\in{\mathbb{Z}^+}\setminus\{1,3\}$ , and showing that there are no graphs $G$ with $γ_{\rm gr}^t(G)\in \{1,3\}$ . We also present such a family, which has minimum possible order and size among all graphs with Grundy total domination number equal to $k$ .

preprint2015arXiv

On the Packing Chromatic Number on Hamming Graphs and General Graphs

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ needed to proper color the vertices of $G$ in such a way the distance between any two vertices having color $i$ be at least $i+1$ . We obtain $χ_ρ(H_{q,m})$ for $m=3$ , where $H_{q,m}$ is the Hamming graph of words of length $m$ and alphabet with $q$ symbols, and tabulate bounds of them for $m \geq 4$ up to 10000 vertices. We also give a polynomial reduction from the problem of finding $χ_ρ(G)$ to the Maximum Stable Set problem.

preprint2014arXiv

An exact DSatur-based algorithm for the Equitable Coloring Problem

This paper describes an exact algorithm for the Equitable Coloring Problem, based on the well known DSatur algorithm for the classic Coloring Problem with new pruning rules specifically derived from the equity constraint. Computational experiences show that our algorithm is competitive with those known in literature.

preprint2014arXiv

The Identifying Code problem on $P_4$ -tidy graphs

In this paper we first analyze the behaviour of the identifying code number under union and join operations in graphs. This study forced us to analyze three new parameters related to identifying codes, dominating sets and total dominating sets of the complementary graph. We obtain closed formulas for these parameters on spider and quasi-spider graphs. These results easily derive in a linear dynamic programming-based algorithm for the Identifying Code problem for $P_4$ -tidy graphs.

preprint2012arXiv

Some advances on the set covering polyhedron of circulant matrices

Working on the set covering polyhedron of consecutive ones circulant matrices, Argiroffo and Bianchi found a class of facet defining inequalities, induced by a particular family of circulant minors. In this work we extend these results to inequalities associated with every circulant minor. We also obtain polynomial separation algorithms for particular classes of such inequalities.

preprint2011arXiv

A polyhedral approach for the Equitable Coloring Problem

In this work we study the polytope associated with a 0,1-integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence that shows the efficacy of these inequalities used in a cutting-plane algorithm.

preprint2011arXiv

Polyhedral results for the Equitable Coloring Problem

In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Graciela Nasini

Research overview

Is this your work?

8 publications

A Branch and Price Algorithm for List Coloring Problem

Total dominating sequences in trees, split graphs, and under modular decomposition

On the Packing Chromatic Number on Hamming Graphs and General Graphs

An exact DSatur-based algorithm for the Equitable Coloring Problem

The Identifying Code problem on $P_4$ -tidy graphs

Some advances on the set covering polyhedron of circulant matrices

A polyhedral approach for the Equitable Coloring Problem

Polyhedral results for the Equitable Coloring Problem

See the researcher in context

Building this map preview

Graciela Nasini

Research overview

Is this your work?

8 publications

A Branch and Price Algorithm for List Coloring Problem

Total dominating sequences in trees, split graphs, and under modular decomposition

On the Packing Chromatic Number on Hamming Graphs and General Graphs

An exact DSatur-based algorithm for the Equitable Coloring Problem

The Identifying Code problem on P4P_4P4​-tidy graphs

Some advances on the set covering polyhedron of circulant matrices

A polyhedral approach for the Equitable Coloring Problem

Polyhedral results for the Equitable Coloring Problem

See the researcher in context

Building this map preview

The Identifying Code problem on $P_4$ -tidy graphs