Josep Díaz

Comput. Sci. Rev., 2020

On List k-Coloring Convex Bipartite Graphs.

[BibT_eX]

[DOI]

CoRR, 2020

2019

EATCS Fellows 2020 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2019

Algorithmically Efficient Syntactic Characterization of Possibility Domains.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions.

[BibT_eX]

[DOI]

Mordecai J. Golin

Proceedings of the Approximation, 2019

2018

EATCS Fellows 2019 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2018

Smoothed Analysis of the Expected Number of Maximal Points in Two Dimensions.

[BibT_eX]

[DOI]

Mordecai J. Golin

CoRR, 2018

2017

Complexity of metric dimension on planar graphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

The social cost of congestion games by imposing variable delays.

[BibT_eX]

[DOI]

ICT Express, 2017

Minimum bisection is NP-hard on unit disk graphs.

[BibT_eX]

[DOI]

George B. Mertzios

Inf. Comput., 2017

2016

Absorption time of the Moran process.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

On the Stability of Generalized Second Price Auctions with Budgets.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

2014

On the relation between graph distance and Euclidean distance in random geometric graphs.

[BibT_eX]

[DOI]

CoRR, 2014

Optimizing the Social Cost of Congestion Games by Imposing Variable Delays.

[BibT_eX]

[DOI]

CoRR, 2014

Approximating Fixation Probabilities in the Generalized Moran Process.

[BibT_eX]

[DOI]

Algorithmica, 2014

2013

The Power of Choice for Random Satisfiability.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Continuous monitoring in the dynamic sensor field model.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

A personal account of Turing's imprint on the development of computer science.

[BibT_eX]

[DOI]

Carme Torras

Comput. Sci. Rev., 2012

Book Review: George Dyson "Turing's Cathedral: The Origins of the Digital Universe" (2012) Pantheon Books.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2012

Can Fixation be Guaranteed in the Generalized Moran Process?

[BibT_eX]

[DOI]

CoRR, 2012

On the Complexity of Metric Dimension.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

2011

Theoretical Aspects of Graph Models for MANETs.

[BibT_eX]

[DOI]

Paolo Santi

Proceedings of the Theoretical Aspects of Distributed Computing in Sensor Networks, 2011

Editorial.

[BibT_eX]

[DOI]

Tiziana Calamoneri

J. Discrete Algorithms, 2011

Cris Moore, Stephen Mertens, , The Nature of Computation (2011) Oxford UP.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2011

Planar Metric Dimension is NP-complete

[BibT_eX]

[DOI]

Olli Pottonen

Erik Jan van Leeuwen

CoRR, 2011

Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks.

[BibT_eX]

[DOI]

Alberto Marchetti-Spaccamela

Paolo Santi

Julinda Stefa

Proceedings of the Algorithms - ESA 2011, 2011

2010

A note on the subgraphs of the (2×∞)-grid.

[BibT_eX]

[DOI]

Marcin Kaminski

Discret. Math., 2010

The cook-book approach to the differential equation method.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2010

Book review.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2010

2009

Large Connectivity for Dynamic Random Geometric Graphs.

[BibT_eX]

[DOI]

IEEE Trans. Mob. Comput., 2009

On the satisfiability threshold of formulas with three literals per clause.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Balanced cut approximation in random geometric graphs.

[BibT_eX]

[DOI]

Alberto Marchetti-Spaccamela

Fabrizio Grandoni

Theor. Comput. Sci., 2009

On the chromatic number of a random 5-regular graph.

[BibT_eX]

[DOI]

J. Graph Theory, 2009

Introduction.

[BibT_eX]

[DOI]

Jarik Nesetril

Comput. Sci. Rev., 2009

On the Power of Mediators.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

Paradigms for fast parallel approximability (Reprint from 1997).

[BibT_eX]

[DOI]

Cambridge international series on parallel computation 8, Cambridge University Press, ISBN: 978-0-521-43170-5, 2009

2008

High level communication functionalities for wireless sensor networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Walkers on the Cycle and the Grid.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2008

Efficient algorithms for counting parameterized list H-colorings.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

The distant-2 chromatic number of random proximity and random geometric graphs.

[BibT_eX]

[DOI]

Zvi Lotker

Inf. Process. Lett., 2008

On the Probability of the Existence of Fixed-Size Components in Random Geometric Graphs

[BibT_eX]

[DOI]

CoRR, 2008

On the connectivity of dynamic random geometric graphs.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

A new upper bound for 3-SAT.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

2007

Bounds on the bisection width for random d -regular graphs.

[BibT_eX]

[DOI]

Nicholas C. Wormald

Theor. Comput. Sci., 2007

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

[BibT_eX]

[DOI]

Marcin Kaminski

Theor. Comput. Sci., 2007

Communication tree problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Sharp Threshold for Hamiltonicity of Random Geometric Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2007

Complexity issues on bounded restrictive H-coloring.

[BibT_eX]

[DOI]

Discret. Math., 2007

Editorial.

[BibT_eX]

[DOI]

Jan Kratochvíl

Jirí Fiala

Discret. Appl. Math., 2007

Dynamic Random Geometric Graphs

[BibT_eX]

[DOI]

CoRR, 2007

2006

Kernels for the Vertex Cover Problem on the Preferred Attachment Model.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms, 5th International Workshop, 2006

Fast FPT-Algorithms for Cleaning Grids.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

2005

The chromatic and clique numbers of random scaled sector graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Preface.

[BibT_eX]

[DOI]

Juhani Karhumäki

Theor. Comput. Sci., 2005

Adversarial models for priority-based networks.

[BibT_eX]

[DOI]

Networks, 2005

The restrictive <i>H</i>-coloring problem.

[BibT_eX]

[DOI]

Dionisios G. Sotiropoulos

Discret. Appl. Math., 2005

Connectivity for Wireless Agents Moving on a Cycle or Grid.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

5-Regular Graphs are 3-Colorable with Positive Probability.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

2004

The complexity of deciding stability under FFS in the Adversarial Queueing model.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

Efficient and reliable high level communication in randomly deployed wireless sensor networks.

[BibT_eX]

[DOI]

Proceedings of the Second International Workshop on Mobility Management & Wireless Access Protocols, 2004

Computation of the Bisection Width for Random d-Regular Graphs.

[BibT_eX]

[DOI]

Nicholas C. Wormald

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

2003

A Random Graph Model for Optical Networks of Sensors.

[BibT_eX]

[DOI]

IEEE Trans. Mob. Comput., 2003

Bounds on the max and min bisection of random cubic and random 4-regular graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Evaluation of Basic Protocols for Optical Smart Dust Networks.

[BibT_eX]

[DOI]

Proceedings of the Experimental and Efficient Algorithms, Second International Workshop, 2003

2002

Counting H-colorings of partial k-trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Analysis of Algorithms (AofA): Part I: 1993 -- 1998.

[BibT_eX]

Bull. EATCS, 2002

Primes in P (Without Assumptions).

[BibT_eX]

Bull. EATCS, 2002

A survey of graph layout problems.

[BibT_eX]

[DOI]

ACM Comput. Surv., 2002

The Complexity of Restrictive H-Coloring.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Bisection of Random Cubic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

H-Colorings of Large Degree Graphs.

[BibT_eX]

[DOI]

Jaroslav Nesetril

Proceedings of the EurAsia-ICT 2002: Information and Communication Technology, 2002

2001

Approximating Layout Problems on Random Geometric Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 2001

H-Colorings of Graphs.

[BibT_eX]

Bull. EATCS, 2001

Approximating layout problems on random graphs.

[BibT_eX]

[DOI]

Discret. Math., 2001

The hardness of intervalizing four colored caterpillars.

[BibT_eX]

[DOI]

Carme Àlvarez

Discret. Math., 2001

Stability and non-stability of the FIFO protocol.

[BibT_eX]

[DOI]

Dimitrios Koukopoulos

Sotiris E. Nikoletseas

Paul G. Spirakis

Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

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

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Recent Results on Parameterized H-Colorings.

[BibT_eX]

[DOI]

Proceedings of the Graphs, 2001

2000

Faulty Random Geometric Networks.

[BibT_eX]

[DOI]

Parallel Process. Lett., 2000

Convergence Theorems For Some Layout Measures On Random Lattice And Random Geometric Graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2000

Routing Tree Problems on Random Graphs.

[BibT_eX]

Proceedings of the ICALP Workshops 2000, 2000

1999

Linear Orderings of Random Geometric Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

Layout Problems on Lattice Graphs.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

On the Random Generation and Counting of Matchings in Dense Graphs.

[BibT_eX]

[DOI]

Paul G. Spirakis

Theor. Comput. Sci., 1998

Random Geometric Problems on [0, 1]².

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

1997

Parallel Algorithms for the Minimum Cut and the Minimum Length Tree Layout Problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1997

Linear and nonlinear systems: A survey.

[BibT_eX]

[DOI]

Paul G. Spirakis

Proceedings of the Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, 1997

Algorithms for Learning Finite Automata from Queries: A Unified View.

[BibT_eX]

Ricard Gavaldà

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996

An Optimal Parallel Algorithm for Learning DFA.

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 1996

Parallel Approximation Schemes for Problems on Planar Graphs.

[BibT_eX]

[DOI]

Acta Informatica, 1996

1995

Structural Complexity I, Second Edition

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 354058384X, 1995

Efficient Parallel Algorithms for some Tree Layout Problems.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994

The Query Complexity of Learning DFA.

[BibT_eX]

[DOI]

New Gener. Comput., 1994

1993

Average-Case Analysis on Simple Families of Trees Using a Balanced Probability Model.

[BibT_eX]

[DOI]

Conrado Martinez

Theor. Comput. Sci., 1993

Parallel Approximation Schemes for problems on planar graphs (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

1992

On the Average Size of the Intersection of Binary Trees.

[BibT_eX]

[DOI]

Ricardo A. Baeza-Yates

Conrado Martinez

SIAM J. Comput., 1992

Graph Layout Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

A Note on the Query Complexity of Learning DFA (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, Third Workshop, 1992

1991

The MINSUMCUT Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 1991

Static on Random Trees.

[BibT_eX]

[DOI]

Conrado Martinez

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

1990

Structural Complexity II

[BibT_eX]

[DOI]

EATCS Monographs on Theoretical Computer Science 22, Springer, ISBN: 0387520791, 1990

Structural Complexity I

[BibT_eX]

[DOI]

EATCS Monographs on Theoretical Computer Science 11, Springer, ISBN: 978-3-642-97062-7, 1990

Classes of Bounded Nondeterminism.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1990

1989

Average-Case Analysis of Robinson's Unification Algorithm with Two Different Variables.

[BibT_eX]

[DOI]

Jean-Marc Steyaert

Inf. Process. Lett., 1989

Complexity Classes with Complete Problems Between P and NP-C.

[BibT_eX]

[DOI]

Carme Àlvarez

Proceedings of the Fundamentals of Computation Theory, 1989

1988

Structural complexity, 1st Edition.

[BibT_eX]

[DOI]

José Luis Balcázar

EATCS monographs on theoretical computer science 11, Springer, ISBN: 0387186220, 1988

1987

On Characterizations of the Class PSPACE/POLY.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1987

1986

On Non- uniform Polynomial Space.

[BibT_eX]

[DOI]

Proceedings of the Structure in Complexity Theory, 1986

1985

Uniform Characterizations of Non-Uniform Complexity Measures

[BibT_eX]

[DOI]

Inf. Control., 1985

Examples of CFI-BI-immune and CF-levelable sets in logspace.

[BibT_eX]

Bull. EATCS, 1985

On some "non-uniform" complexity measures.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1985

1984

Some results about Logspace complexity measures.

[BibT_eX]

Bull. EATCS, 1984

1982

A Solution of the Sperner-Erdös Problem.

[BibT_eX]

[DOI]

Xavier Berenguer

Lawrence H. Harper

Theor. Comput. Sci., 1982

A Note on a Theorem by Ladner.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1982

1980

The Weighted Sperner's Set Problem.

[BibT_eX]

[DOI]

Xavier Berenguer