15 citations · 86 across the 65 of their papers we have counts for
70 papers
Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem
Argyrios Deligkas, Eduard Eiben, Gregory Gutin +2
We introduce and study a new optimization problem on digraphs, termed Maximum Weighted Digraph Partition (MWDP) problem. We prove three complexity dichotomies for MWDP: on arbitrar…
Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems
Argyrios Deligkas, Eduard Eiben, Gregory Gutin +2
We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordinati…
Bounds on Maximum Weight Directed Cut
Jiangdong Ai, Stefanie Gerke, Gregory Gutin +2
We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses.…
(1,1)-Cluster Editing is Polynomial-time Solvable
Gregory Gutin, Anders Yeo
A graph is a clique graph if is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the -{Cluster Editing} problem, where for fixed natural numbers ,…
Results on the Small Quasi-Kernel Conjecture
Jiangdong Ai, Stefanie Gerke, Gregory Gutin +2
A {\em quasi-kernel} of a digraph is an independent set such that for every vertex , there exists a directed path with one or two arcs…
Finding all stable matchings with assignment constraints
Gregory Gutin, Philip R. Neary, Anders Yeo
In this paper we consider stable matchings subject to assignment constraints. These are matchings that require certain assigned pairs to be included, insist that some other assigne…