2024
Packing and Covering a Given Directed Graph in a Directed Graph.
SIAM J. Discret. Math., March, 2024
Highly Connected Graphs Have Highly Connected Spanning Bipartite Subgraphs.
Electron. J. Comb., 2024
2023
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
2022
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, Ser. B, 2022
Ramsey number of 1-subdivisions of transitive tournaments.
J. Comb. Theory, Ser. B, 2022
The Covering Threshold of a Directed Acyclic Graph by Directed Acyclic Subgraphs.
Electron. J. Comb., 2022
2021
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
2020
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
2019
On the exact maximum induced density of almost all graphs and their inducibility.
J. Comb. Theory, Ser. B, 2019
The removal lemma for tournaments.
J. Comb. Theory, Ser. 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
2018
The Effect of Local Majority on Global Majorityin Connected Graphs.
Graphs Comb., 2018
2017
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
2016
Encyclopedia of Algorithms, 2016
Approximating the Diameter of Planar Graphs in Near Linear Time.
ACM Trans. Algorithms, 2016
J. Comb. Theory, Ser. B, 2016
On Zero-Sum and Almost Zero-Sum Subgraphs Over ℤ.
Graphs Comb., 2016
2015
Packing edge-disjoint triangles in regular and almost regular tournaments.
Discret. Math., 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. 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
2013
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, 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.
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
2012
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
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
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
2010
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, Ser. 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
2009
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
2008
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
Matrix Sparsification for Rank and Determinant Computations via Nested Dissection.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2007
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
2006
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
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
2005
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, Ser. 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
2004
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, Ser. 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
2003
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
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.
Discret. Math., 2002
A Note on the Number of Edges Guaranteeing a C4 in Eulerian Bipartite Digraphs.
Electron. J. Comb., 2002
2001
Covering Non-uniform Hypergraphs.
J. Comb. Theory, Ser. B, 2001
Large Monotone Paths in Graphs with Bounded Degree.
Graphs Comb., 2001
Monotone paths in edge-ordered sparse graphs.
Discret. Math., 2001
2000
Connected Domination and Spanning Trees with Many Leaves.
SIAM J. Discret. Math., 2000
Packing and Decomposition of Graphs with Trees.
J. Comb. Theory, Ser. B, 2000
J. Comb. Theory, Ser. 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
1999
Decomposing large graphs with small graphs of high density.
J. Graph Theory, 1999
Orthogonal Decomposition and Packing of Complete Graphs.
J. Comb. Theory, Ser. 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
1998
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, Ser. A, 1998
Linear coloring of graphs.
Discret. Math., 1998
1997
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, Ser. 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
1996
The number of edge colorings with no monochromatic triangle.
J. Graph Theory, 1996
<i>H</i>-Factors in Dense Graphs.
J. Comb. Theory, Ser. B, 1996
1995
The 123 Theorem and Its Extensions.
J. Comb. Theory, Ser. A, 1995
1994
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
1993
Threshold Functions for H-factors.
Comb. Probab. Comput., 1993
1992
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
