36 citations · 61 across the 14 of their papers we have counts for
7 papers · 1 filter
The Multicolored Graph Realization Problem
Josep Díaz, Öznur Yaşar Diner, Maria Serna +1
We introduce the Multicolored Graph Realization problem (MGRP). The input to the problem is a colored graph , i.e., a graph together with a coloring on its vertices. We can…
On List k-Coloring Convex Bipartite Graphs
Josep Díaz, Öznur Yaşar Diner, Maria Serna +1
List k-Coloring (Li k-Col) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..,k…
Algorithmically Efficient Syntactic Characterization of Possibility Domains
Josep Díaz, Lefteris Kirousis, Sofia Kokonezi +1
In the field of Judgment Aggrgation, a domain, that is a subset of a Cartesian power of , is considered to reflect abstract rationality restrictions on vectors of two-valu…
Minimum Bisection is NP-hard on Unit Disk Graphs
Josep Diaz, George B. Mertzios
In this paper we prove that the \textsc{Min-Bisection} problem is NP-hard on \emph{unit disk graphs}, thus solving a longstanding open question.
The Power of Choice for Random Satisfiability
Varsha Dani, Josep Diaz, Thomas Hayes +1
We consider Achlioptas processes for k-SAT formulas. We create a semi-random formula with n variables and m clauses, where each clause is a choice, made on-line, between two or mor…
Approximating Fixation Probabilities in the Generalized Moran Process
Josep Díaz, Leslie Ann Goldberg, George B. Mertzios +3
We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected g…