On-line Available Papers of Raphael Yuster

1992   1993   1994   1995   1996   1997   1998   1999   2000   2001   2002   2003   2004   2005   2006   2007   2008   2009   2010   Preprints

1992    top

  1. N. Alon and R. Yuster
    Almost H-factors in dense graphs
    Graphs and Combinatorics 8 (1992), 95-102

  2. N. Alon, R. A. Duke, H. Lefmann, V. Rodl, and R. Yuster
    The algorithmic aspects of the Regularity Lemma
    Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE (1992), 473-481
    Journal version: Journal of Algorithms 16 (1994), 80-109

1993    top

  1. N. Alon and R. Yuster
    Threshold functions for H-factors
    Combinatorics, Probability and Computing 2 (1993), 137-144

1994    top

  1. R. Yuster and U. Zwick
    Finding even cycles even faster
    Proceedings of the 21st International Colloquium on Automata, Languages and Programming (ICALP), Springer Verlag (1994), 532-543
    Journal version: SIAM Journal on Discrete Mathematics 10 (1997), 209-222

  2. N. Alon, R. Yuster, and U. Zwick
    Color Coding
    Proceedings of the 26th ACM Symposium on the Theory of Computing (STOC), ACM Press (1994), 326-335
    Journal version: Journal of the ACM 42 (1995), 844-856

  3. N. Alon, R. Yuster, and U. Zwick
    Finding and counting given length cycles
    Proceedings of the 2nd Annual European Symposium on Algorithms (ESA), Springer Verlag (1994), 354-364
    Journal version: Algorithmica 17 (1997), 209-223

1995    top

  1. N. Alon and R. Yuster
    The 123 Theorem and its extensions
    Journal of Combinatorial Theory, Series A 72 (1995), 322-331

1996    top

  1. N. Alon and R. Yuster
    H-factors in dense graphs
    Journal of Combinatorial Theory, Series B 66 (1996), 269-282

  2. R. Yuster
    The number of edge colorings with no monochromatic triangle
    Journal of Graph Theory 21 (1996) 441-452

1997    top

  1. Y. Caro and R. Yuster
    Packing Graphs: The packing problem solved
    The Electronic Journal of Combinatorics 4 (1997), #R1

  2. R. Yuster
    A note on packing trees into complete bipartite graphs
    Discrete Mathematics 163 (1997), 325-327

  3. Y. Caro and R. Yuster
    Efficient covering designs of the complete graph
    The Electronic Journal of Combinatorics 4 (1997), #R10

  4. R. Yuster
    Independent transversals and independent coverings in sparse partite graphs
    Combinatorics, Probability and Computing 6 (1997), 115-125

  5. R. Yuster
    Independent transversals in r-partite graphs
    Discrete Mathematics 176 (1997), 255-261

  6. Y. Caro and R. Yuster
    Recognizing Global occurrence of local properties
    Journal of Complexity 13 (1997), 340-352

  7. N. Alon, Y. Caro, and R. Yuster
    Packing the edges of a graph by a prescribed tree with minimum overlap
    Journal of Combinatorial Theory, Series B 71 (1997), 144-161

1998    top

  1. R. Yuster
    Linear coloring of graphs
    Discrete Mathematics 185 (1998), 293-297

  2. R. Yuster
    Tree decomposition of graphs
    Random Structures and Algorithms 12 (1998), 237-251

  3. Y. Caro and R. Yuster
    Covering graphs: The covering problem solved
    Journal of Combinatorial Theory, Series A, 83 (1998), 273-282

  4. N. Alon, Y. Caro, and R. Yuster
    Packing and covering of dense graphs
    Journal of Combinatorial Designs 6 (1998), 451-472

  5. Y. Caro and R. Yuster
    The characterization of zero-sum (mod 2) bipartite Ramsey numbers
    Journal of Graph Theory 29 (1998), 151-166

1999    top

  1. Y. Caro and R. Yuster
    Orthogonal coloring of graphs
    The Electronic Journal of Combinatorics 6 (1999), #R5

  2. Y. Caro and R. Yuster,
    Graph decomposition of slim graphs
    Graphs and Combinatorics 15 (1999), 5-19

  3. R. Yuster
    Optimal factorizations of families of trees
    Discrete Mathematics 203 (1999), 291-297

  4. Y. Caro and R. Yuster
    The uniformity space of hypergraphs and its applications
    Discrete Mathematics 202 (1999), 1-19

  5. R. Yuster
    Decomposing large graphs with small graphs of high density
    Journal of Graph Theory 32 (1999) 27-40

  6. Y. Caro and R. Yuster
    Orthogonal decomposition and packing of complete graphs
    Journal of Combinatorial Theory, Series A 88 (1999), 93-111

  7. Y. Caro and R. Yuster
    On graphs having the local decomposition property
    Ars Combinatoria, 52 (1999), 115-124

2000    top

  1. Y. Caro, A. Bialostocki, G. Bialostocki, and R. Yuster
    Zero-sum ascending waves
    Journal of Combinatorial Mathematics and Combinatorial Computing 32 (2000), 103-114

  2. Y. Caro and R. Yuster
    Intersecting designs
    Journal of Combinatorial Theory, Series A 89 (2000), 113-125

  3. R. Yuster
    Decomposing hypergraphs into simple hypertrees
    Combinatorica 20 (2000), 119-140

  4. R. Yuster
    Packing and decomposition of graphs with trees
    Journal of Combinatorial Theory, Series B 78 (2000), 123-140

  5. Y. Caro, D. West, and R. Yuster
    Connected domination and spanning trees with many leaves
    SIAM Journal on Discrete Mathematics 13 (2000), 202-211

  6. Y. Caro and R. Yuster
    A Turan Type problem concerning the powers of the degrees of a graph
    The Electronic Journal of Combinatorics 7 (2000), #R47

  7. N. Alon and R. Yuster
    Every H-decomposition has a near-resolvable alternative
    European Journal of Combinatorics 21 (2000), 839-845

  8. R. Yuster
    Arithmetic progressions with constant weight
    Discrete Mathematics 224 (2000), 225-237

  9. Y. Caro and R. Yuster
    Dominating a family of graphs with small connected subgraphs
    Combinatorics, Probability and Computing 9 (2000), 309-313

  10. Y. Caro and R. Yuster
    Graphs with large variance
    Ars Combinatoria 57 (2000), 151-162

2001    top

  1. Y. Roditty, B. Shoham, and R. Yuster
    Monotone paths in edge-ordered sparse graphs
    Discrete Mathematics 226 (2001), 411-417

  2. E. Boros, Y. Caro, Z. Furedi, and R. Yuster
    Covering non-uniform hypergraphs
    Journal of Combinatorial Theory, Series B 82 (2001), 270-284

  3. R. Yuster
    Large monotone paths in graphs with bounded degree
    Graphs and Combinatorics 17 (2001), 579-587

  4. Y. Caro and R. Yuster
    Orthogonal H-decompositions
    Bulletin of the ICA 33 (2001), 42-48

2002    top

  1. Y. Caro and R. Yuster
    List decomposition of graphs
     Discrete Mathematics 243 (2002), 67-77

  2. J. Shen and R. Yuster
    A note on the number of edges guaranteeing a C4 in Eulerian bipartite digraphs
    The Electronic Journal of Combinatorics 9 (2002), #N6

  3. R. Yuster
    The decomposition threshold of bipartite graphs with minimum degree one
    Random Structures and Algorithms 21 (2002), 121-134

  4. P. Balister, Y. Caro, C. Rousseau, and R. Yuster
    Zero sum square matrices
    European Journal of Combinatorics 23 (2002), 489-497

2003    top

  1. G. Chen, J. Shen, and R. Yuster
    Second neighborhood via first neighborhood in digraphs
    Annals of Combinatorics 7 (2003), 15-20

  2. Y. Caro and R. Yuster
    2-connected graphs with small 2-connected dominating sets
    Discrete Mathematics 269 (2003), 265-271

  3. R. Yuster
    A note on graphs without k-connected subgraphs
    Ars Combinatoria 67 (2003), 231-235

  4. R. Yuster
    Equitable coloring of k-uniform hypergraphs
    SIAM Journal on Discrete Mathematics 16 (2003), 524-532

  5. Y. Caro and R. Yuster
    The order of monochromatic subgraphs with a given minimum degree
    The Electronic Journal of Combinatorics 10 (2003), #R32

  6. N. Alon, S. Litsyn, and R. Yuster
    A coding theory bound and zero-sum square matrices
    Graphs and Combinatorics 19 (2003), 449-457

  7. R. Yuster
    Tiling transitive tournaments and their blow-ups
    Order 20 (2003), 121-133

2004    top

  1. R. Yuster and U. Zwick
    Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
    Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press (2004), 247-253

  2. R. Yuster
    Nowhere 0 mod p dominating sets in multigraphs
    Ars Combinatoria 70 (2004), 309-318

  3. D. Archdeacon, J. Ellis-Monaghan, D. Fisher, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, and R. Yuster
    Some remarks on domination
    Journal of Graph Theory 46 (2004), 207-210

  4. Y. Caro and R. Yuster
    Edge-coloring complete uniform hypergraphs with many components
    Journal of Combinatorial Theory, Series B 91 (2004), 215-227

  5. R. Yuster
    Families of trees decompose the random graph in an arbitrary way
    Combinatorics, Probability and Computing 13 (2004), 893-910

  6. N. Alon, G. Kaplan, A. Lev, Y. Roditty, and R. Yuster
    Dense graphs are antimagic
    Journal of Graph Theory 47 (2004), 297-309

  7. Z. Nutov and R. Yuster
    Packing directed cycles efficiently
    Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS), Springer Verlag (2004), 310-321
    Journal version: (Special Issue) Discrete Applied Mathematics 155 (2007), 82–91

  8. R. Yuster and U. Zwick
    Fast sparse matrix multiplication
    Proceedings of the 12th Annual European Symposium on Algorithms (ESA), Springer Verlag (2004), 604-615
    Journal version: ACM Transactions on Algorithms 1 (2005), 2-13

  9. R. Yuster
    The number of edge-disjoint transitive triples in a tournament
    Discrete Mathematics 287 (2004), 187-191

2005    top

  1. R. Yuster
    Integer and fractional packing of families of graphs
    Random Structures and Algorithms 26 (2005), 110-118

  2. R. Yuster
    Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs
    Annals of Combinatorics 9 (2005), 117-124

  3. M. Krivelevich, Z. Nutov, and R. Yuster
    Approximation algorithms for cycle packing problems
    Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press (2005), 556-561
    Journal version (with M. Salavatipour and J. Verstraete): ACM Transcations on Algorithms 3 (2007), 48:1-48:21

  4. R. Yuster
    Asymptotically optimal Kk packings of dense graphs via fractional Kk decompositions
    Journal of Combinatorial Theory, Series B 95 (2005), 1-11

  5. Y. Caro, W.F. Klostermeyer, and R. Yuster
    Connected odd dominating sets
    Discuss. Math. Graph Theory 25 (2005), 225-239

  6. R. Yuster
    Fractional decompositions of dense hypergraphs
    Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM), Springer Verlag (2005), 482-493
    Journal version: Bulletin of the London Mathematical Society 39 (2007), 156-166

  7. R. Yuster and U. Zwick
    Answering distance queries in directed graphs using fast matrix multiplication
    Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE (2005), 389-396

  8. N. Alon and R. Yuster
    On a hypergraph matching problem
    Graphs and Combinatorics 21 (2005), 377-384

2006    top

  1. N. Alon and R. Yuster
    The number of orientations having no fixed tournament
    Combinatorica 26 (2006), 1-16

  2. R. Yuster
    Decomposing oriented graphs into transitive tournaments
    Discrete Mathematics 306 (2006), 166-170

  3. R. Yuster
    Rainbow H-factors
    The Electronic Journal of Combinatorics 13 (2006), #R13

  4. I. Beniaminy, Z. Nutov, and R. Yuster
    A (1-1/e)-approximation algorithm for the maximum generalized assignment problem with fixed profits
    Operations Research Letters 34 (2006), 283-288

  5. R. Yuster
    Finding and counting cliques and independent sets in r-uniform hypergraphs
    Information Processing Letters 99 (2006), 130-134

  6. V. Vassilevska, R. Williams, and R. Yuster
    Finding the smallest H-subgraph in real weighted graphs and related problems
    Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), Springer Verlag (2006), 262-273

  7. R. Yuster
    Mean Ramsey-Turan numbers
    Journal of Graph Theory 53 (2006), 126-134

2007    top

  1. R. Yuster and U. Zwick
    Maximum matching in graphs with an excluded minor
    Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press (2007), 108-117

  2. A. Shapira, R. Yuster, and U. Zwick
    All pairs bottleneck paths in vertex weighted graphs
    Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press (2007), 978-985

  3. D. Fidler and R. Yuster
    Remarks on the second neighborhood problem
    Journal of Graph Theory 55 (2007), 208-220

  4. V. Vassilevska, R. Williams, and R. Yuster
    All-Pairs bottleneck paths for general graphs in truly sub-cubic time
    Proceedings of the 39th ACM Symposium on the Theory of Computing (STOC), ACM Press (2007), 585-589
    Journal version: Theory of Computing 5 (2009), 173-189

  5. R. Yuster
    Packing cliques in graphs with independence number 2
    Combinatorics, Probability, and Computing 16 (2007), 805-817

  6. R. Yuster
    Almost exact matchings
    Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Springer Verlag (2007), 286-295

  7. F. Chataigner, G. Manic, Y. Wakabayashi, and R. Yuster
    Approximation algorithms and hardness results for the clique packing problem
    Proceedings of the 4th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), Electronic Notes in Discrete Mathematics 29 (2007), 397-401
    Journal version: Discrete Applied Mathematics 157 (2009), 1396-1406

  8. R. Yuster
    Combinatorial and computational aspects of graph packing and graph decomposition
    Computer Science Review 1 (2007), 12-26

  9. N. Alon and R. Yuster
    Fast algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in graphs with a (not so) small vertex cover
    Proceedings of the 15th Annual European Symposium on Algorithms (ESA), Springer Verlag (2007), 175-186

2008    top

  1. R. Yuster
    Rainbow decompositions
    Proceedings of the American Mathematical Society 136 (2008), 771-779

  2. A. Shapira and R. Yuster
    The effect of induced subgraphs on quasi-randomness
    Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press (2008), 789-798
    Journal version: Random Structures and Algorithms 36 (2010), 90-109

  3. R. Yuster
    Almost given length cycles in digraphs
    Graphs and Combinatorics 24 (2008), 59-65

  4. R. Yuster
    All-pairs disjoint paths from a common ancestor in O(nw) time
    Theoretical Computer Science 396 (2008) 145–150

  5. Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster
    On rainbow connection
    The Electronic Journal of Combinatorics 15 (2008), #R57

  6. R. Yuster
    Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
    Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM), Springer Verlag (2008), 596-601

  7. M. Kabiya and R. Yuster
    Packing transitive triples in a tournament
    Annals of Combinatorics 12 (2008), 291-306

  8. R. Yuster
    Disjoint color-avoiding triangles
    SIAM Journal on Discrete Mathematics 23 (2008), 195-204

  9. R. Yuster
    Matrix sparsification for rank and determinant computations via nested dissection
    Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE (2008), 137-145

2009    top

  1. R. Yuster
    Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
    Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press (2009), 950-957

  2. Y. Caro and R. Yuster
    Large disjoint subgraphs with the same order and size
    European Journal of Combinatorics 30 (2009), 813-821

  3. S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster
    Hardness and algorithms for rainbow connectivity
    Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), Dagstuhl Seminar Proceedings (2009), 243-254

  4. A. Shapira and R. Yuster
    Multigraphs (only) satisfy a weak triangle removal lemma
    The Electronic Journal of Combinatorics 16 (2009), #N11

  5. T. Mansour, C. Song, and R. Yuster
    A comment on Ryser's conjecture for intersecting hypergraphs
    Graphs and Combinatorics 25 (2009), 101-109

  6. O. Weimann and R. Yuster
    Computing the girth of a planar graph in O(n log n) time
    Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Springer Verlag (2009), 764-773

2010    top

  1. R. Yuster
    Generating a d-dimensional linear subspace efficiently
    Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM (2010), 467-470

  2. S. Snir and R. Yuster
    Reconstructing approximate phylogenetic trees from quartet samples
    Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM (2010), 1035-1044

  3. Y. Caro and R. Yuster
    Large induced subgraphs with equated maximum degree
    Discrete Mathematics 310 (2010), 742-747

  4. M. Krivelevich and R. Yuster
    The rainbow connection of a graph is (at most) reciprocal to its minimum degree
    Journal of Graph Theory 63 (2010), 185-191

Preprints    top

  1. S. Chakraborty, E. Fischer, O. Lachish, and R. Yuster
    Two-phase algorithms for the parametric shortest path problem
    Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), Dagstuhl Seminar Proceedings (2010), to appear