37 citations · 89 across the 11 of their papers we have counts for
7 papers · 1 filter
Complexity of solving a system of difference constraints with variables restricted to a finite set
Santiago Cifuentes, Francisco J. Soulignac, Pablo Terlisky
Fishburn developed an algorithm to solve a system of difference constraints whose unknowns must take values from a set with real numbers [Solving a system of difference…
Total 2-domination of proper interval graphs
Francisco J. Soulignac
A set of vertices of a graph is a total -dominating set when every vertex of has at least neighbors in . In a recent article, Chiarelli et al.\ (Improved Algo…
The eternal dominating set problem for interval graphs
Martín Rinemberg, Francisco J. Soulignac
We prove that, in games in which all the guards move at the same turn, the eternal domination and the clique-connected cover numbers coincide for interval graphs. A linear algorith…
Minimal and minimum unit circular-arc models
Francisco J. Soulignac, Pablo Terlisky
A proper circular-arc (PCA) model is a pair where is a circle and is a family of inclusion-free arcs on in which no two arcs of c…
Bounded, minimal, and short representations of unit interval and unit circular-arc graphs
Francisco J. Soulignac
We consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version, a proper circula…
Disimplicial arcs, transitive vertices, and disimplicial eliminations
Martiniano Eguía, Francisco J. Soulignac
In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A diclique of a d…
Subclasses of Normal Helly Circular-Arc Graphs
Min Chih Lin, Francisco J. Soulignac, Jayme L. Szwarcfiter
A Helly circular-arc model M = (C,A) is a circle C together with a Helly family \A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, i…