Raphael Yuster

According to our database1, Raphael Yuster authored at least 149 papers between 1992 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Acyclic subgraphs with high chromatic number.
Eur. J. Comb., 2019

Vector clique decompositions.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
The Effect of Local Majority on Global Majorityin Connected Graphs.
Graphs and Combinatorics, 2018

2017
A Ramsey type result for oriented trees.
Eur. J. Comb., 2017

Ramsey numbers for degree monotone paths.
Discrete Mathematics, 2017

On the longest path of a randomly weighted tournament.
Discrete Applied Mathematics, 2017

On the Maximum Number of Spanning Copies of an Orientation in a Tournament.
Combinatorics, Probability & Computing, 2017

2016
Color Coding.
Encyclopedia of Algorithms, 2016

Unavoidable tournaments.
J. Comb. Theory, Ser. B, 2016

On Zero-Sum and Almost Zero-Sum Subgraphs Over ℤ.
Graphs and Combinatorics, 2016

2015
Packing edge-disjoint triangles in regular and almost regular tournaments.
Discrete Mathematics, 2015

2014
Approximating the maximum consecutive subsums of a sequence.
Theor. Comput. Sci., 2014

Edge-Disjoint Cliques in Graphs with High Minimum Degree.
SIAM J. Discrete Math., 2014

Forcing $k$-repetitions in Degree Sequences.
Electr. J. Comb., 2014

On Minimum Witnesses for Boolean Matrix Multiplication.
Algorithmica, 2014

On the compatibility of quartet trees.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication.
ACM Trans. Algorithms, 2013

Packing Triangles in Regular Tournaments.
Journal of Graph Theory, 2013

The Turán number of sparse spanning graphs.
J. Comb. Theory, Ser. B, 2013

Matrix sparsification and nested dissection over arbitrary fields.
J. ACM, 2013

Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs.
Combinatorics, Probability & Computing, 2013

Edge-Disjoint Induced Subgraphs with Given Minimum Degree.
Electr. J. Comb., 2013

Maximum Matching in Regular and Almost Regular Graphs.
Algorithmica, 2013

Approximating the Diameter of Planar Graphs in Near Linear Time.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
The quasi-randomness of hypergraph cut properties.
Random Struct. Algorithms, 2012

Approximate shortest paths in weighted graphs.
J. Comput. Syst. Sci., 2012

Dense Graphs With a Large Triangle Cover Have a Large Triangle Packing.
Combinatorics, Probability & Computing, 2012

Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence.
Proceedings of the Combinatorial Pattern Matching - 23rd Annual Symposium, 2012

2011
On graphs and algebraic graphs that do not contain cycles of length 4.
Journal of Graph Theory, 2011

Hardness and algorithms for rainbow connection.
J. Comb. Optim., 2011

A shortest cycle for each vertex of a graph.
Inf. Process. Lett., 2011

Colorful monochromatic connectivity.
Discrete Mathematics, 2011

On the Size of Dissociated Bases.
Electr. J. Comb., 2011

Equitable Hypergraph Orientations.
Electr. J. Comb., 2011

Distance Oracles for Vertex-Labeled Graphs.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Single source shortest paths in H-minor free graphs.
Theor. Comput. Sci., 2010

Finding heaviest H-subgraphs in real weighted graphs, with applications.
ACM Trans. Algorithms, 2010

Computing the Girth of a Planar Graph in O(n logn) Time.
SIAM J. Discrete Math., 2010

The rainbow connection of a graph is (at most) reciprocal to its minimum degree.
Journal of Graph Theory, 2010

On the density of a graph and its blowup.
J. Comb. Theory, Ser. B, 2010

Large induced subgraphs with equated maximum degree.
Discrete Mathematics, 2010

Two-phase Algorithms for the Parametric Shortest Path Problem.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Generating a d-dimensional Linear Subspace Efficiently.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Reconstructing Approximate Phylogenetic Trees from Quartet Samples.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Replacement Paths via Fast Matrix Multiplication.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Solving Linear Systems through Nested Dissection.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time.
Theory of Computing, 2009

A Comment on Ryser's Conjecture for Intersecting Hypergraphs.
Graphs and Combinatorics, 2009

Large disjoint subgraphs with the same order and size.
Eur. J. Comb., 2009

Approximation algorithms and hardness results for the clique packing problem.
Discrete Applied Mathematics, 2009

Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma.
Electr. J. Comb., 2009

Hardness and Algorithms for Rainbow Connectivity.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Efficient algorithms on sets of permutations, dominance, and real-weighted APSP.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Computing the Girth of a Planar Graph in O(n logn) Time.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008
Color Coding.
Proceedings of the Encyclopedia of Algorithms, 2008

All-pairs disjoint paths from a common ancestor in O~(ninfinit) time.
Theor. Comput. Sci., 2008

Disjoint Color-Avoiding Triangles.
SIAM J. Discrete Math., 2008

Almost Given Length Cycles in Digraphs.
Graphs and Combinatorics, 2008

On Rainbow Connection.
Electr. J. Comb., 2008

The effect of induced subgraphs on quasi-randomness.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Matrix Sparsification for Rank and Determinant Computations via Nested Dissection.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets.
Proceedings of the Approximation, 2008

2007
Approximation algorithms and hardness results for cycle packing problems.
ACM Trans. Algorithms, 2007

Remarks on the second neighborhood problem.
Journal of Graph Theory, 2007

Approximation algorithms and hardness results for the clique packing problem.
Electronic Notes in Discrete Mathematics, 2007

Combinatorial and computational aspects of graph packing and graph decomposition.
Computer Science Review, 2007

Packing Cliques in Graphs with Independence Number 2.
Combinatorics, Probability & Computing, 2007

All-pairs bottleneck paths for general graphs in truly sub-cubic time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Maximum matching in graphs with an excluded minor.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

All-pairs bottleneck paths in vertex weighted graphs.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover.
Proceedings of the Algorithms, 2007

Almost Exact Matchings.
Proceedings of the Approximation, 2007

2006
A (1-1/e)-approximation algorithm for the generalized assignment problem.
Oper. Res. Lett., 2006

Mean Ramsey-Turán numbers.
Journal of Graph Theory, 2006

Finding and counting cliques and independent sets in r-uniform hypergraphs.
Inf. Process. Lett., 2006

Decomposing oriented graphs into transitive tournaments.
Discrete Mathematics, 2006

Rainbow H-factors.
Electr. J. Comb., 2006

The Number Of Orientations Having No Fixed Tournament.
Combinatorica, 2006

Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
Integer and fractional packing of families of graphs.
Random Struct. Algorithms, 2005

Asymptotically optimal Kk-packings of dense graphs via fractional Kk-decompositions.
J. Comb. Theory, Ser. B, 2005

On a Hypergraph Matching Problem.
Graphs and Combinatorics, 2005

Connected odd dominating sets in graphs.
Discussiones Mathematicae Graph Theory, 2005

Approximation algorithms for cycle packing problems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Answering distance queries in directed graphs using fast matrix multiplication.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Fractional Decompositions of Dense Hypergraphs.
Proceedings of the Approximation, 2005

2004
Some remarks on domination.
Journal of Graph Theory, 2004

Dense graphs are antimagic.
Journal of Graph Theory, 2004

Edge coloring complete uniform hypergraphs with many components.
J. Comb. Theory, Ser. B, 2004

The number of edge-disjoint transitive triples in a tournament.
Discrete Mathematics, 2004

Families of Trees Decompose the Random Graph in an Arbitrary Way.
Combinatorics, Probability & Computing, 2004

Nowhere 0 mod p dominating sets in multigraphs.
Ars Comb., 2004

Detecting short directed cycles using rectangular matrix multiplication and dynamic programming.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Packing Directed Cycles Efficiently.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Fast Sparse Matrix Multiplication.
Proceedings of the Algorithms, 2004

2003
Equitable Coloring of k-Uniform Hypergraphs.
SIAM J. Discrete Math., 2003

Tiling Transitive Tournaments and Their Blow-ups.
Order, 2003

A Coding Theory Bound and Zero-Sum Square Matrices.
Graphs and Combinatorics, 2003

2-connected graphs with small 2-connected dominating sets.
Discrete Mathematics, 2003

The Order of Monochromatic Subgraphs with a Given Minimum Degree.
Electr. J. Comb., 2003

A note on graphs without k-connected subgraphs.
Ars Comb., 2003

2002
The decomposition threshold for bipartite graphs with minimum degree one.
Random Struct. Algorithms, 2002

Zero-sum Square Matrices.
Eur. J. Comb., 2002

List decomposition of graphs.
Discrete Mathematics, 2002

A Note on the Number of Edges Guaranteeing a C4 in Eulerian Bipartite Digraphs.
Electr. J. Comb., 2002

2001
Covering Non-uniform Hypergraphs.
J. Comb. Theory, Ser. B, 2001

Large Monotone Paths in Graphs with Bounded Degree.
Graphs and Combinatorics, 2001

Monotone paths in edge-ordered sparse graphs.
Discrete Mathematics, 2001

2000
Connected Domination and Spanning Trees with Many Leaves.
SIAM J. Discrete Math., 2000

Packing and Decomposition of Graphs with Trees.
J. Comb. Theory, Ser. B, 2000

Intersecting Designs.
J. Comb. Theory, Ser. A, 2000

EveryH-decomposition ofKnhas a Nearly Resolvable Alternative.
Eur. J. Comb., 2000

Arithmetic progressions with constant weight.
Discrete Mathematics, 2000

Dominating A Family Of Graphs With Small Connected Subgraphs.
Combinatorics, Probability & Computing, 2000

A Tura'n Type Problem Concerning the Powers of the Degrees of a Graph.
Electr. J. Comb., 2000

Decomposing Hypergraphs into Simple Hypertrees.
Combinatorica, 2000

Graphs with Large Variance.
Ars Comb., 2000

1999
Decomposing large graphs with small graphs of high density.
Journal of Graph Theory, 1999

Orthogonal Decomposition and Packing of Complete Graphs.
J. Comb. Theory, Ser. A, 1999

Graph Decomposition of Slim Graphs.
Graphs and Combinatorics, 1999

Optimal factorizations of families of trees.
Discrete Mathematics, 1999

The uniformity space of hypergraphs and its applications.
Discrete Mathematics, 1999

Orthogonal Colorings of Graphs.
Electr. J. Comb., 1999

Graphs Having the Local Decomposition Property.
Ars Comb., 1999

1998
Tree decomposition of graphs.
Random Struct. Algorithms, 1998

The characterization of zero-sum (mod 2) bipartite Ramsey numbers.
Journal of Graph Theory, 1998

Covering Graphs: The Covering Problem Solved.
J. Comb. Theory, Ser. A, 1998

Linear coloring of graphs.
Discrete Mathematics, 1998

1997
Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap.
J. Comb. Theory, Ser. B, 1997

Recognizing Global Occurrence of Local Properties.
J. Complexity, 1997

On packing trees into complete bipartite graphs.
Discrete Mathematics, 1997

Independent transversals in r-partite graphs.
Discrete Mathematics, 1997

Independent Transversals and Independent Coverings in Sparse Partite Graphs.
Combinatorics, Probability & Computing, 1997

Efficient Covering Designs of the Complete Graph.
Electr. J. Comb., 1997

Packing Graphs: The packing problem solved.
Electr. J. Comb., 1997

Finding and Counting Given Length Cycles.
Algorithmica, 1997

1996
The number of edge colorings with no monochromatic triangle.
Journal of Graph Theory, 1996

H-Factors in Dense Graphs.
J. Comb. Theory, Ser. B, 1996

1995
The 123 Theorem and Its Extensions.
J. Comb. Theory, Ser. A, 1995

Color-Coding.
J. ACM, 1995

1994
The Algorithmic Aspects of the Regularity Lemma.
J. Algorithms, 1994

Color-Coding
Electronic Colloquium on Computational Complexity (ECCC), 1994

Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Finding Even Cycles Even Faster.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Finding and Counting Given Length Cycles (Extended Abstract).
Proceedings of the Algorithms, 1994

1993
Threshold Functions for H-factors.
Combinatorics, Probability & Computing, 1993

1992
AlmostH-factors in dense graphs.
Graphs and Combinatorics, 1992

The Algorithmic Aspects of the Regularity Lemma (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992


  Loading...