Josep Díaz

I&C Journal 2017 Journal Article

Minimum bisection is NP-hard on unit disk graphs

• Josep Díaz
• George B. Mertzios

In this paper we prove that the Min-Bisection problem is NP-hard on unit disk graphs, thus solving a longstanding open question.

SODA Conference 2012 Conference Paper

Approximating fixation probabilities in the generalized Moran process

• Josep Díaz
• Leslie Ann Goldberg
• George B. Mertzios
• David Richerby
• Maria J. Serna
• Paul G. Spirakis

TCS Journal 2008 Journal Article

High level communication functionalities for wireless sensor networks

• Carme Àlvarez
• Josep Díaz
• Jordi Petit
• José Rolim
• Maria Serna

In this paper we show how to establish a reliable and efficient high level communication system in a randomly deployed network of sensors equipped with directional antennas. This high level communication system enables the programming of the sensor network using high level communication functionalities without the burden of taking care of their physical capacities (low range, unidirectional links, single frequency, presence of collisions, etc.). The high level communication functionalities we offer include point-to-point communication, point-to-area communication, and one-to-all communication. The basic idea to implement this system is to simulate a virtual network that emerges from the ad-hoc network using self-organization, self-discovery and collaborative methods. We also analyse the efficiency, scalability and robustness of the proposed protocols.

SODA Conference 2008 Conference Paper

On the connectivity of dynamic random geometric graphs

• Josep Díaz
• Dieter Mitsche
• Xavier Pérez-Giménez

TCS Journal 2007 Journal Article

Communication tree problems

• Carme Àlvarez
• Rafel Cases
• Josep Díaz
• Jordi Petit
• Maria Serna

In this paper, we deal with the problem of constructing optimal communication trees satisfying given communication requirements. We consider two constant degree tree communication models and several cost measures. First, we analyze whether a tree selected at random provides a good randomized approximation algorithm, and we show that such a construction fails for some of the measures. Secondly, we provide approximation algorithms for the case in which the communication requirements are given by a random graph in two different random models, namely the classical G n, p and random geometric graphs. Finally, we conclude with some open problems.

TCS Journal 2007 Journal Article

MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs

• Josep Díaz
• Marcin Kamiński

We prove that the max-cut and max-bisection problems are NP-hard on unit disk graphs. We also show that λ -precision graphs are planar for λ > 1 / 2 and give a dichotomy theorem for max-cut computational complexity on λ -precision unit disk graphs.

TCS Journal 2005 Journal Article

Preface

• Josep Díaz
• Juhani Karhumaki

TCS Journal 2005 Journal Article

The chromatic and clique numbers of random scaled sector graphs

• Josep Díaz
• Vishal Sanwalani
• Maria Serna
• Paul G. Spirakis

Random scaled sector graphs were introduced as a generalization of random geometric graphs to model networks of sensors using optical communication. In the random scaled sector graph model vertices are placed uniformly at random into the [ 0, 1 ] 2 unit square. Each vertex i is assigned uniformly at random sector S i, of central angle α i, in a circle of radius r i (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in S i. In this work, we study the value of the chromatic number χ ( G n ), directed clique number ω ( G n ), and undirected clique number ω 2 ^ ( G n ) for random scaled sector graphs with n vertices, where each vertex spans a sector of α degrees with radius r n = ln n n. We prove that for values α < π, as n → ∞ w. h. p. , χ ( G n ) and ω 2 ^ ( G n ) are Θ ( ln n ln ln n ), while ω ( G n ) is O ( 1 ), showing a clear difference with the random geometric graph model. For α > π w. h. p. , χ ( G n ) and ω 2 ^ ( G n ) are Θ ( ln n ), being the same for random scaled sector and random geometric graphs, while ω ( G n ) is Θ ( ln n ln ln n ).

MFCS Conference 2003 Conference Paper

Adversarial Models for Priority-Based Networks

• Carme Àlvarez
• Maria J. Blesa
• Josep Díaz
• Antonio Fernández 0001
• Maria J. Serna

Abstract We propose several variations of the adversarial queueing model to cope with packets that can have different priorities, the priority and variable priority models, and link failures, the failure and reliable models. We address stability issues in the proposed adversarial models. We show that the set of universally stable networks in the adversarial model remains the same in the four introduced models. From the point of view of queueing policies we show that several queueing policies that are universally stable in the adversarial model remain so in the priority, failure and reliable models. However, we show that lis, a universally stable queueing policy in the adversarial model, is not universally stable in any of the other models, and that no greedy queueing policy is universally stable in the variable priority model. Finally we analyze the problem of deciding stability of a given network under a fixed protocol. We provide a characterization of the networks that are stable under fifo and lis in the failure model. This characterization allows us to show that deciding network stability under fifo and lis in the proposed models can be solved in polynomial time.

TCS Journal 2002 Journal Article

Counting H-colorings of partial k-trees

• Josep Díaz
• Maria Serna
• Dimitrios M. Thilikos

The problem of counting all H-colorings of a graph G with n vertices is considered. While the problem is, in general, #P-complete, we give linear time algorithms that solve the main variants of this problem when the input graph G is a k-tree or, in the case where G is directed, when the underlying graph of G is a k-tree. Our algorithms remain polynomial even in the case where k=O(log n) or in the case where the size of H is O(n). Our results are easy to implement and imply the existence of polynomial time algorithms for a series of problems on partial k-trees such as core checking and chromatic polynomial computation.

MFCS Conference 2001 Conference Paper

(H, C, K)-Coloring: Fast, Easy, and Hard Cases

• Josep Díaz
• Maria J. Serna
• Dimitrios M. Thilikos

Abstract We define a variant of the H -coloring problem by fixing the number of preimages of a subset C of the vertices of H, thus allowing parameterization. We provide sufficient conditions to guarantee that the problem can be solved in O(kn + f(k, H)) steps where f is a function depending only on the number k of fixed preimages and the graph H, and in O ( n k+c ) steps where c is a constant independent of k. Finally, we prove that whenever the non parameterized vertices induce in G a graph that is bipartite and loopless the problem is NP-complete.

TCS Journal 1997 Journal Article

Parallel algorithms for the minimum cut and the minimum length tree layout problems

• Josep Díaz
• Alan Gibbons
• Grammati E. Pantziou
• Maria J. Serna
• Paul G. Spirakis
• Jacobo Toran

The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two parallel algorithms for the CREW PRAM. The first solves the minimum length linear arrangement problem for trees and the second solves the minimum cut arrangement for trees. We prove that the first problem belongs to NC for trees, and the second problem is in NC for bounded degree trees. To the best of our knowledge, these are the first parallel algorithms for the minimum length and the minimum cut linear arrangement problems.

MFCS Conference 1992 Invited Paper

Graph Layout Problems

• Josep Díaz

Abstract In this paper we survey the recent results and open questions about some graph layout problems.

MFCS Conference 1980 Conference Paper

The Weighted Sperner's Set Problem

• Xavier Berenguer
• Josep Díaz

Abstract A polynomial time bounded algorithm is presented for solving the Weighted Sperner's Set Problem, that is, the problem of computing an independent Set of maximal weight on a weighted partially ordered set.