Tomás Feder

Eur. J. Comb., 2021

2020

Complexity of correspondence H-colourings.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2020

List Homomorphism Problems for Signed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints.

[BibT_eX]

[DOI]

CoRR, 2019

2018

Distance-Two Colorings of Barnette Graphs.

[BibT_eX]

[DOI]

CoRR, 2018

Distance-Two Coloring of Barnette Graphs.

[BibT_eX]

[DOI]

Proceedings of the 30th Canadian Conference on Computational Geometry, 2018

2017

Correspondence Homomorphisms to Reflexive Graphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2017

Colourings, homomorphisms, and partitions of transitive digraphs.

[BibT_eX]

[DOI]

César Hernández-Cruz

Eur. J. Comb., 2017

Dichotomy for Digraph Homomorphism Problems.

[BibT_eX]

[DOI]

Arash Rafiey

Jeff Kinne

CoRR, 2017

Complexity of Correspondence Homomorphisms.

[BibT_eX]

[DOI]

CoRR, 2017

2014

Graphs Admitting k-NU Operations. Part 2: The Irreflexive Case.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Matrix partitions of split graphs.

[BibT_eX]

[DOI]

Oren Shklarsky

Discret. Appl. Math., 2014

2013

Graphs Admitting k-NU Operations. Part 1: The Reflexive Case.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Edge-coloring almost bipartite multigraphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

Obstructions to partitions of chordal graphs.

[BibT_eX]

[DOI]

Shekoofeh Nekooei Rizi

Discret. Math., 2013

On hypercube labellings and antipodal monochromatic paths.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2013

2012

Distributing Data for Secure Database Services.

[BibT_eX]

[DOI]

Trans. Data Priv., 2012

On the Complexity of MMSNP.

[BibT_eX]

[DOI]

Manuel Bodirsky

Hubie Chen

SIAM J. Discret. Math., 2012

Packing Edge-Disjoint Triangles in Given Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

2011

Maximum gap labelings of graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

Partitioning Chordal Graphs.

[BibT_eX]

[DOI]

Shekoofeh Nekooei Rizi

Electron. Notes Discret. Math., 2011

Dichotomy for tree-structured trigraph list homomorphism problems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

2010

Achieving anonymity via clustering.

[BibT_eX]

[DOI]

Krishnaram Kenthapadi

Samir Khuller

An Zhu

ACM Trans. Algorithms, 2010

Retractions to Pseudoforests.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

2009

Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Approximating the Minimum Chain Completion problem.

[BibT_eX]

[DOI]

Heikki Mannila

Evimaria Terzi

Inf. Process. Lett., 2009

On the graph turnpike problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Adjusted Interval Digraphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2009

Extension problems with degree bounds.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

2008

Brooks-Type Theorems for Pair-List Colorings and List Homomorphisms.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2008

Near-Unanimity Functions and Varieties of Reflexive Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2008

Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

On realizations of point determining graphs, and obstructions to full homomorphisms.

[BibT_eX]

[DOI]

Discret. Math., 2008

Anonymizing Graphs

[BibT_eX]

[DOI]

Shubha U. Nabar

Evimaria Terzi

CoRR, 2008

2007

Querying priced information in databases: The conjunctive case.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

Computing shortest paths with uncertainty.

[BibT_eX]

[DOI]

J. Algorithms, 2007

Matrix Partitions with Finitely Many Obstructions.

[BibT_eX]

[DOI]

Wing Xie

Electron. Notes Discret. Math., 2007

The structure of bi-arc trees.

[BibT_eX]

[DOI]

Discret. Math., 2007

List homomorphisms of graphs with bounded degrees.

[BibT_eX]

[DOI]

Discret. Math., 2007

Approximating nash equilibria using small-support strategies.

[BibT_eX]

[DOI]

Hamid Nazerzadeh

Amin Saberi

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

2006

Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection.

[BibT_eX]

[DOI]

Daniel K. Ford

SIAM J. Discret. Math., 2006

A Dichotomy Theorem on Fixed Points of Several Nonexpansive Mappings.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2006

Full Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

k-connected spanning subgraphs of low degree.

[BibT_eX]

[DOI]

An Zhu

Electron. Colloquium Comput. Complex., 2006

Finding large cycles in Hamiltonian graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Closures and dichotomies for quantified constraints.

[BibT_eX]

[DOI]

Phokion G. Kolaitis

Electron. Colloquium Comput. Complex., 2006

Channel assignment in wireless networks and classification of minimum graph homomorphism.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Constraint satisfaction: a personal perspective.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Partition into k-vertex subgraphs of k-partite graphs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

On Barnette's conjecture

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Matrix partitions of perfect graphs.

[BibT_eX]

[DOI]

Discret. Math., 2006

Digraph matrix partitions and trigraph homomorphisms.

[BibT_eX]

[DOI]

Kim Tucker-Nally

Discret. Appl. Math., 2006

A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

List matrix partitions of chordal graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Disks on a Tree: Analysis of a Combinatorial Game.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

Constraint Satisfaction on Finite Groups with Near Subgroups

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Two algorithms for general list matrix partitions.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Algorithms for the Database Layout Problem.

[BibT_eX]

[DOI]

Proceedings of the Database Theory, 2005

Anonymizing Tables.

[BibT_eX]

[DOI]

Gagan Aggarwal

Krishnaram Kenthapadi

Proceedings of the Database Theory, 2005

2004

Dichotomies for classes of homomorphism problems involving unary functions.

[BibT_eX]

[DOI]

Florent R. Madelaine

Iain A. Stewart

Theor. Comput. Sci., 2004

Combining request scheduling with web caching.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Incremental Clustering and Dynamic Information Retrieval.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

List Partitions of Chordal Graphs.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Algorithms for Multi-product Pricing.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Acyclic Homomorphisms and Circular Colorings of Digraphs.

[BibT_eX]

[DOI]

Bojan Mohar

SIAM J. Discret. Math., 2003

List Partitions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2003

Computing the Median with Uncertainty.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Bi-arc graphs and the complexity of list homomorphisms.

[BibT_eX]

[DOI]

J. Graph Theory, 2003

A combinatorial algorithm for MAX CSP.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

Representing Graph Metrics with Fewest Edges.

[BibT_eX]

[DOI]

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Homomorphism Closed vs. Existential Positive.

[BibT_eX]

[DOI]

Moshe Y. Vardi

Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

2002

Approximating the Longest Cycle Problem in Sparse Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

Worst-case time bounds for coloring and satisfiability problems.

[BibT_eX]

[DOI]

J. Algorithms, 2002

Web caching with request reordering.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

Fanout limitations on constraint systems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2001

2000

A sublinear parallel algorithm for stable matching.

[BibT_eX]

[DOI]

Nimrod Megiddo

Serge A. Plotkin

Theor. Comput. Sci., 2000

Finding long paths and cycles in sparse Hamiltonian graphs.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

List Homomorphisms and Circular Arc Graphs.

[BibT_eX]

[DOI]

Comb., 1999

Complexity of Graph Partition Problems.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory.

[BibT_eX]

[DOI]

Moshe Y. Vardi

SIAM J. Comput., 1998

List Homomorphisms to Reflexive Graphs.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 1998

Online Channel Allocation in FDMA Networks with Reuse Constraints.

[BibT_eX]

[DOI]

Sunil M. Shende

Inf. Process. Lett., 1998

1996

The Benefits of Relaxing Punctuality.

[BibT_eX]

[DOI]

Rajeev Alur

Thomas A. Henzinger

J. ACM, 1996

1995

Amortized Communication Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

Clique Partitions, Graph Compression and Speeding-Up Algorithms.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

1994

Network Flow and 2-Satisfiability.

[BibT_eX]

[DOI]

Algorithmica, 1994

1993

Monotone monadic SNP and constraint satisfaction.

[BibT_eX]

[DOI]

Moshe Y. Vardi

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992

Determinism vs. Nondeterminism in Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Danny Dolev

SIAM J. Comput., 1992

Product graph representations.

[BibT_eX]

[DOI]

J. Graph Theory, 1992

A New Fixed Point Approach for Stable Networks and Stable Marriages.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

Balanced Matroids

[BibT_eX]

[DOI]

Milena Mihail

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Decidability and Undecidability of Equivalence for Linear Datalog with Applications to Normal-Form Optimizations.

[BibT_eX]

[DOI]

Yatin P. Saraiya

Proceedings of the Database Theory, 1992

1991

Stable networks and product graphs.

[BibT_eX]

[DOI]

PhD thesis, 1991

Amortized Communication Complexity (Preliminary Version)

[BibT_eX]

[DOI]

Eyal Kushilevitz

Moni Naor

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1989

Reliable computation by networks in the presence of noise.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1989

Multiparty Communication Complexity

[BibT_eX]

[DOI]

Danny Dolev

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

Optimal Algorithms for Approximate Clustering

[BibT_eX]

[DOI]