Raphael Yuster

Orcid: 0000-0001-7550-6506

  • University of Haifa, Israel

According to our database1, Raphael Yuster authored at least 173 papers between 1992 and 2024.

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



In proceedings 
PhD thesis 


Online presence:

On csauthors.net:


Packing and Covering a Given Directed Graph in a Directed Graph.
SIAM J. Discret. Math., March, 2024

Path-monochromatic bounded depth rooted trees in (random) tournaments.
Discret. Math., 2024

Highly Connected Graphs Have Highly Connected Spanning Bipartite Subgraphs.
Electron. J. Comb., 2024

Sum-distinguishing number of sparse hypergraphs.
Eur. J. Comb., August, 2023

The number of bounded-degree spanning trees.
Random Struct. Algorithms, May, 2023

Counting Homomorphic Cycles in Degenerate Graphs.
ACM Trans. Algorithms, January, 2023

Finding and counting small tournaments in large tournaments.
CoRR, 2023

On the quartet distance given partial information.
J. Graph Theory, 2022

Hamiltonian cycles above expectation in <i>r</i>-graphs and quasi-random <i>r</i>-graphs.
J. Comb. Theory B, 2022

Ramsey number of 1-subdivisions of transitive tournaments.
J. Comb. Theory B, 2022

The Covering Threshold of a Directed Acyclic Graph by Directed Acyclic Subgraphs.
Electron. J. Comb., 2022

All Feedback Arc Sets of a Random Turán Tournament Have $\lfloor {n}/{k}\rfloor-{k}+1$ Disjoint k-Cliques (and This Is Tight).
SIAM J. Discret. Math., 2021

Paths with many shortcuts in tournaments.
Discret. Math., 2021

On Factors of Independent Transversals in $k$-Partite Graphs.
Electron. J. Comb., 2021

A 2<sup><i>O</i>(<i>k</i>)</sup><i>n</i> algorithm for <i>k</i>-cycle in minor-closed graph families.
Theor. Comput. Sci., 2020

Incremental distance products via faulty shortest paths.
Inf. Process. Lett., 2020

Induced subgraphs with many repeated degrees.
Discret. Math., 2020

Perfect sequence covering arrays.
Des. Codes Cryptogr., 2020

A 2<sup>O(k)</sup>n algorithm for k-cycle in minor-closed graph families.
CoRR, 2020

Covering Small Subgraphs of (Hyper)Tournaments with Spanning Acyclic Subgraphs.
Electron. J. Comb., 2020

On the exact maximum induced density of almost all graphs and their inducibility.
J. Comb. Theory B, 2019

The removal lemma for tournaments.
J. Comb. Theory B, 2019

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

Clumsy Packings of Graphs.
Electron. J. Comb., 2019

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

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

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

Ramsey numbers for degree monotone paths.
Discret. Math., 2017

On the longest path of a randomly weighted tournament.
Discret. Appl. Math., 2017

On the Maximum Number of Spanning Copies of an Orientation in a Tournament.
Comb. Probab. Comput., 2017

Color Coding.
Encyclopedia of Algorithms, 2016

Approximating the Diameter of Planar Graphs in Near Linear Time.
ACM Trans. Algorithms, 2016

Unavoidable tournaments.
J. Comb. Theory B, 2016

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

Packing edge-disjoint triangles in regular and almost regular tournaments.
Discret. Math., 2015

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

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

On the Compatibility of Quartet Trees.
SIAM J. Discret. Math., 2014

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

On Minimum Witnesses for Boolean Matrix Multiplication.
Algorithmica, 2014

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

Packing Triangles in Regular Tournaments.
J. Graph Theory, 2013

The Turán number of sparse spanning graphs.
J. Comb. Theory 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.
Comb. Probab. Comput., 2013

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

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

Reconstructing Approximate Phylogenetic Trees from Quartet Samples.
SIAM J. Comput., 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.
Comb. Probab. Comput., 2012

Almost Exact Matchings.
Algorithmica, 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

A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs.
SIAM J. Discret. Math., 2011

On graphs and algebraic graphs that do not contain cycles of length 4.
J. 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.
Discret. Math., 2011

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

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

All-Pairs Bottleneck Paths in Vertex Weighted Graphs.
Algorithmica, 2011

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

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

Finding heaviest <i>H</i>-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. Discret. Math., 2010

The effect of induced subgraphs on quasi-randomness.
Random Struct. Algorithms, 2010

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

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

Large induced subgraphs with equated maximum degree.
Discret. Math., 2010

Computing the diameter polynomially faster than APSP
CoRR, 2010

Two-phase algorithms for the parametric shortest path problem
CoRR, 2010

Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets.
Comb., 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

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

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

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

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

Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma.
Electron. 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 <i>O</i>(<i>n</i> log<i>n</i>) Time.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

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

All-pairs disjoint paths from a common ancestor in O~(n<sup>infinit</sup>) time.
Theor. Comput. Sci., 2008

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

Almost Given Length Cycles in Digraphs.
Graphs Comb., 2008

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

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

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

Remarks on the second neighborhood problem.
J. Graph Theory, 2007

Approximation algorithms and hardness results for the clique packing problem.
Electron. Notes Discret. Math., 2007

Packing directed cycles efficiently.
Discret. Appl. Math., 2007

Combinatorial and computational aspects of graph packing and graph decomposition.
Comput. Sci. Rev., 2007

Packing Cliques in Graphs with Independence Number 2.
Comb. Probab. Comput., 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

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

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

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

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

Decomposing oriented graphs into transitive tournaments.
Discret. Math., 2006

Finding heaviest H-subgraphs in real weighted graphs, with applications
CoRR, 2006

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

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

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

Fast sparse matrix multiplication.
ACM Trans. Algorithms, 2005

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

Asymptotically optimal <i>K</i><sub><i>k</i></sub>-packings of dense graphs via fractional <i>K</i><sub><i>k</i></sub>-decompositions.
J. Comb. Theory B, 2005

On a Hypergraph Matching Problem.
Graphs Comb., 2005

Connected odd dominating sets in graphs.
Discuss. Math. 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

Some remarks on domination.
J. Graph Theory, 2004

Dense graphs are antimagic.
J. Graph Theory, 2004

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

The number of edge-disjoint transitive triples in a tournament.
Discret. Math., 2004

Families of Trees Decompose the Random Graph in an Arbitrary Way.
Comb. Probab. Comput., 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

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

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

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

2-connected graphs with small 2-connected dominating sets.
Discret. Math., 2003

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

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

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.
Discret. Math., 2002

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

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

Large Monotone Paths in Graphs with Bounded Degree.
Graphs Comb., 2001

Monotone paths in edge-ordered sparse graphs.
Discret. Math., 2001

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

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

Intersecting Designs.
J. Comb. Theory A, 2000

Every<i>H</i>-decomposition of<i>K<sub>n</sub></i>has a Nearly Resolvable Alternative.
Eur. J. Comb., 2000

Arithmetic progressions with constant weight.
Discret. Math., 2000

Dominating A Family Of Graphs With Small Connected Subgraphs.
Comb. Probab. Comput., 2000

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

Decomposing Hypergraphs into Simple Hypertrees.
Comb., 2000

Graphs with Large Variance.
Ars Comb., 2000

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

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

Graph Decomposition of Slim Graphs.
Graphs Comb., 1999

Optimal factorizations of families of trees.
Discret. Math., 1999

The uniformity space of hypergraphs and its applications.
Discret. Math., 1999

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

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

Tree decomposition of graphs.
Random Struct. Algorithms, 1998

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

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

Linear coloring of graphs.
Discret. Math., 1998

Finding Even Cycles Even Faster.
SIAM J. Discret. Math., 1997

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

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

On packing trees into complete bipartite graphs.
Discret. Math., 1997

Independent transversals in r-partite graphs.
Discret. Math., 1997

Independent Transversals and Independent Coverings in Sparse Partite Graphs.
Comb. Probab. Comput., 1997

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

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

Finding and Counting Given Length Cycles.
Algorithmica, 1997

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

<i>H</i>-Factors in Dense Graphs.
J. Comb. Theory B, 1996

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

J. ACM, 1995

The Algorithmic Aspects of the Regularity Lemma.
J. Algorithms, 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 and Counting Given Length Cycles (Extended Abstract).
Proceedings of the Algorithms, 1994

Threshold Functions for H-factors.
Comb. Probab. Comput., 1993

Almost<i>H</i>-factors in dense graphs.
Graphs Comb., 1992

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