37 citations · 89 across the 11 of their papers we have counts for
14 papers
Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
Francisco J. Soulignac
We propose a simple and exact method for the Traveling Salesman Problem with Time Windows and Makespan objective (\TSPTW-M) that solves all instances of the classical benchmark wit…
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…
Loop unrolling of UCA models: distance labeling
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 whose extremes are pairwise different. The model $M…
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…
A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
Francisco J. Soulignac
We present a dynamic algorithm for the recognition of proper circular-arc (PCA) graphs, that supports the insertion and removal of vertices (together with its incident edges). The…
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…
Isomorphism of graph classes related to the circular-ones property
Andrew R. Curtis, Min Chih Lin, Ross M. McConnell +4
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. This algorithm leads to linear-time isomorphism algorithm…
Fully dynamic recognition of proper circular-arc graphs
Francisco J. Soulignac
We present a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. The allowed operations on the graph involve the insertion and removal of vertices (tog…
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…
Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration
Martiniano Eguía, Francisco J. Soulignac
A biclique is a set of vertices that induce a bipartite complete graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every indu…
Arboricity, h-Index, and Dynamic Algorithms
Min Chih Lin, Francisco J. Soulignac, Jayme L. Szwarcfiter
In this paper we present a modification of a technique by Chiba and Nishizeki [Chiba and Nishizeki: Arboricity and Subgraph Listing Algorithms, SIAM J. Comput. 14(1), pp. 210--223…