Zobrazeno 1 - 10
of 71
pro vyhledávání: '"Soulignac, Francisco J"'
Fishburn developed an algorithm to solve a system of $m$ difference constraints whose $n$ unknowns must take values from a set with $k$ real numbers [Solving a system of difference constraints with variables restricted to a finite set, Inform Process
Externí odkaz:
http://arxiv.org/abs/2211.05259
A proper circular-arc (PCA) model is a pair $M = (C, A)$ where $C$ is a circle and $A$ is a family of inclusion-free arcs on $C$ whose extremes are pairwise different. The model $M$ represents a digraph $D$ that has one vertex $v(a)$ for each $a \in
Externí odkaz:
http://arxiv.org/abs/2202.10527
Publikováno v:
In European Journal of Operational Research 1 February 2024 312(3):978-995
Autor:
Soulignac, Francisco J.
A set of vertices $W$ of a graph $G$ is a total $k$-dominating set when every vertex of $G$ has at least $k$ neighbors in $W$. In a recent article, Chiarelli et al.\ (Improved Algorithms for $k$-Domination and Total $k$-Domination in Proper Interval
Externí odkaz:
http://arxiv.org/abs/1812.00689
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 algorithm for the eternal dominating set problem is obtained as a by-product.<
Externí odkaz:
http://arxiv.org/abs/1808.09591
A proper circular-arc (PCA) model is a pair ${\cal M} = (C, \cal A)$ where $C$ is a circle and $\cal A$ is a family of inclusion-free arcs on $C$ in which no two arcs of $\cal A$ cover $C$. A PCA model $\cal U = (C,\cal A)$ is a $(c, \ell)$-CA model
Externí odkaz:
http://arxiv.org/abs/1609.01266
Autor:
Soulignac, Francisco J.
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 main feature of the algorithm is that it outputs a minimally non-PCA i
Externí odkaz:
http://arxiv.org/abs/1509.05828
Publikováno v:
INFORMS Journal on Computing; Jul/Aug2024, Vol. 36 Issue 4, p1064-1083, 20p
Autor:
Soulignac, Francisco J.
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 circular-arc (PCA) model $\cal M$ is given and the goal is to obtain an equiv
Externí odkaz:
http://arxiv.org/abs/1408.3443
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 digraph is a pair $V \to W$ of sets of vertices such that $v \to w$ is
Externí odkaz:
http://arxiv.org/abs/1403.1628