|
2016-present
-
Subgraph counts in
random clustering graphs,
Proceeding of the 19th Workshop on Algorithms and Models for the Web Graph (WAW 2024),
Lecture Notes in Computer Science 14671, Springer, 2024,
pp. 1-16,
(with Nick Sieger).
-
A random graph model for clustering graphs
,
Proceeding of the 18th Workshop on Algorithms and Models for the Web Graph (WAW 2023),
Lecture Notes in Computer Science 13894, Springer, 2023,
pp. 112-126,
(with Nick Sieger).
-
A semi-supervised heat kernel pagerank MBO algorithm for data classification
, Comm. Math. Sci., 16 (2018), 1241--1264,
(with Ekaterina Merkurjev and Andrea L. Bertozzi)
-
Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions, OR Spectrum, 38(2), (2016), 531--540,
(with O. Braun and R. L. Graham).
2011-2015
- Distributed algorithms for finding local clusters using heat kernel pagerank, WAW, 2015,
LNCS 9479, Springer, 177--189,
(with O. Simpson).
-
A brief survey of PageRank algorithms,
IEEE Transactions on Network Science and Engineering, 1, No. 1, (2015), 38--42.
-
Computing heat kernel pagerank and a local clustering algorithms,
Combinatorial Algorithms, Lecture Notes in Comput. Sci., 8986, Springer, Cham, 2015, 110-121,
and the journal version appears in European Journal of Combinatorics, 68 (2018), 96-119,
(with O. Simpson).
-
A chapter titled ``Spectral Graph Theory", to appear in Handbook of Linear Algebra, CCR Press,
(with Steve Butler).
-
From quasirandom graphs to graph limits and graphlets
,
Advances in Applied Math. 56 (2014),
135--174.
-
Solving linear systems with boundary conditions using heat kernel pagerank
WAW 2013, LNCS 8305, 203--219,
(with Olivia Simpson).
The journal version appeared in Internet Mathematics, 11 (2015), 449-471.
-
A local clustering algorithm for connection graphs
,
WAW 2013, LNCS 8305, 203--219,
(with Mark Kempton).
The journal version appeared in Internet Math., 11 (2015), 333-351.
-
Spectral clustering of graphs with general degrees in the extended planted partition model
,
COLT 2012,
Journal of Machine Learning Research, (2012), 1--23,
(with K. Chaudhuri and A. Tsiatas).
-
Multi-commodity allocation for dynamic demands using PageRank vectors
,
WAW2012,
LNCS 7323 (2012), 138--152,
(with P. Horn and J. Hughes).
The journal version appeared in Internet Mathematics, 10 (2014), 49--65.
-
Braess's paradox in expanders
,
Random Structures and Algorithms, 41 (2012), 451--468,
(with S. J. Young and W. Zhao).
-
Hypergraph coloring games and voter models
,
WAW2012, LNCS 7323 (2012), 1--16,
(with Alex Tsiatas).
The
journal version appeared in Internet Mathematics, 10 (2014), 66--86.
-
Edge flipping in graphs,
Advances in Applied Mathematics, 48 (2012) 37--63,
(with Ron Graham).
-
Diameter
of random spanning trees in a given graph ,
Journal of Graph Theory,
69, (2012), 223--240,
(with P. Horn and L. Lu).
-
Dirichlet PageRank and trust-based ranking algorithms,
WAW 2011, LNCS 6732, (2011), 103--114,
(with A. Tsiatas and Wensong Xu).
The journal version,
Dirichlet PageRank and
ranking algorithms based on trust and distrust,
appeared in Internet Mathematics, 9, (2013), 113--134.
-
On the spectra of general random graphs,
Electronic Journal of Combinatorics, 18(1),
(2011), P215, 14 pages,
(with M. Radcliffe).
2006-2010
Back to top
-
Graph Theory in the information age
,
Notices of AMS, 57, no. 6, July 2010, 726--732.
This article was translated into Chinese and appeared in
Mathematical Advances in Translation, 3, 2010, 207--213.
-
A symmetric
Eulerian identity
,
Journal of Combinatorics, 1 (2010), 29--38,
(with Ron Graham and Don Knuth).
-
PageRank and random walks on graphs
,
Fete of Combinatorics and Computer Science, (G. O. H. Katona, A. Schrijver and T. Szonyi, Eds.),
Springer, Berlin, (2010), 43--62,
(with Wenbo Zhao).
-
Finding and visualizing graph clusters using PageRank optimization,
WAW 2010, LNCS 6516, (2010), 86--97,
(with A. Tsiatas).
The journal version appeared in Internet Mathematics, 8 (2012), 46--72,
(with A. Tsiatas).
-
Braess's paradox in large sparse graphs,
WINE 2010, LNCS 6484, 194--208,
(with Stephen J. Young).
-
A sharp PageRank algorithm with applications to edge ranking and graph sparsification
WAW 2010, LNCS 6516, 2--14,
(with Wenbo Zhao).
-
PageRank
as a discrete Green's function,
Geometry and Analysis, I, ALM 17, (2010), 285--302.
-
A local graph
partitioning algorithm using heat kernel pagerank,
WAW 2009,
LNCS 5427, (2009), 62-75.
-
The giant component
in a random subgraph of a given graph
,
Proceedings of WAW2009, Lecture Notes in Computer Science 5427, 38--49,
(with P. Horn and L. Lu).
-
A whirlwind tour of random graphs
,
a survey article in Encyclopedia on Complex Systems, Springer, 2008.
-
A network color game
,
WINE 2008, Lecture Notes in Computer Science, Volume 5385 (2008), 522--530,
(with K. Chaudhuri and M. S. Jamall).
-
Quasi-random graphs with
given degree sequences,
Random Structures and Algorithms, 12 (2008), 1--19,
(with R. L. Graham).
-
Four
Cheeger-type inequalities for graph
partitioning algorithms
,
Proceedings of ICCM, II, (2007), 751--772.
-
The heat kernel as the pagerank of a graph
,
PNAS, 105 (50), (2007), 19735--19740.
-
Local partitioning for directed graphs using PageRank
,
WAW2007, 166--178,
(with R. Andersen and Kevin Lang).
The full paper is in Internet Mathematics, 5 (2008), 3--22.
-
Detecting sharp
drops in PageRank and a simplified local partitioning algorithm
Theory and Applications of Models of Computation,
Proceedings of TAMC 2007, LNCS 4484, Springer, (2007), 1--12,
(with R. Andersen).
-
Random walks and local cuts
in graphs,
Linear Algebra and its Applications, 423 (2007), 22--32.
- Oblivious and adaptive strategies for the majority and plurality problems,
Algorithmica, 48 (2007), 147--157,
(with R. Graham, Jia Mao and Andrew Yao)
-
A brief overview of network algorithms,
J. of Computer and System Sciences 72 (2006), no. 3, 420--424.
2001-2005
Back to top
- Oblivious strategies for the majority and plurality problems,
Computing and Combinatorics, Lecture Notes in Computer Science, Springer, Berlin (2005), 329--338,
(with R. Graham, Jia Mao and Andrew Yao).
The journal version appeared in Algorithmica 48 (2007), 147--157.
-
Drawing power law graphs,
Proceedings Graph Drawing, New York, 2004, 12--17,
(with Reid Andersen, L. Lu).
Paper version, Drawing power law graphs
using a local/global decomposition, appeared in Algorithmica
47 (2007), 379--397.
-
Analyzing
the small world phenomenon using a hybrid model with local network flow,
WAW 2004, Rome, Italy, Lecture Notes in Computer Science,
3234, Springer, 2004, 19--30,
a long version appeared as
Modeling the small-world phenomenon with local network flow,
Internet Mathematics 2 (2006), no. 3, 359--385,
(with Reid Andersen, L. Lu).
- Guessing secrets with inner product questions,
Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, (2002), 247--253,
long version appeared in Internet Math., 1 (2004), no. 2, 177--192,
(with R.L. Graham and Linyuan Lu).
-
Parallelism versus Memory Allocation
in Pipelined Router Forwarding Engines,
SPAA'04, Barcelona, Spain, (2004), 103--111,
(with Ronald Graham and George Varghese).
-
De Bruijn cycles for covering codes,
Random Structures and Algorithms, 25, (2004), 421--431,
(with J. Cooper).
-
On disjoint path pairs with wavelength continuity constraint in WDM networks,
INFOCOM, 2004,
(with Reid Andersen, Arunabha Sen and Guoliang Xue).
-
The average distances in random graphs with given expected degrees,
abstract,
paper (short version),
Proc. National Academy of Sciences 99, no. 25, (December, 2002), 15879--15882,
paper (long version)
,
Internet Mathematics 1 (2003), 91--113,
(with L. Lu).
-
Connected components in random graphs with given expected degree sequences,
abstract,
Annals of Combinatorics 6 (2002), 125-145,
(with L. Lu).
-
A chip-firing game and Dirichlet eigenvalues,
abstract,
Discrete Math 257 (2002), 341--355,
(with Robert Ellis).
-
Guessing secrets,
abstract,
Electronic Journal of Combinatorics 8 (2001), R13, 25 pp,
extended
abstract appeared in
Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms
(Washington, DC, 2001), SIAM, Philadelphia, 723--726,
(with Ron Graham and Tom Leighton).
also, SODA'01, 723--726,
(with Ronald Graham and F. Tom Leighton).
-
Distance realization problems with applications to Internet tomography,
J. Computer and System Sciences 63 No. 3, (November 2001), 432--448,
(with Mark Garrett, Ronald Graham and David Shallcross).
-
The diameter of sparse random graphs,
abstract,
Advances in Applied Math. 26 (2001), 257--279,
(with Linyuan Lu).
-
Dynamic location problems with limited look-ahead,
Theoretical Computer Science 261 (2001), 213--226,
(with Ron Graham).
-
Augmented ring networks,
IEEE Transactions on Parallel and Distributed Systems 12 (2001), 598--609,
(with W. Aiello, S. N. Bhatt, A. L. Rosenberg and R. K. Sitaraman).
1996-2000
Back to top
-
A random graph model for massive graphs,
abstract,
Proceedings of the
Thirtysecond Annual ACM Symposium on Theory of Computing
(2000),
171--180,
(with Bill Aiello and Linyuan Lu).
The complete paper version
has a different title
A random graph model for power law graphs,
Experimental Math. 10 (2001), 53--66.
-
Stratified random walks on an n-cube,
Random Structures and Algorithms 11 (1997), 199--222,
(with R.L. Graham).
-
On optimal strategies for cycle-stealing in networks of workstations,
IEEE Trans. on Computers 46 (1997), 545--557,
(with S. Bhatt, F. T. Leighton, and A. L. Rosenberg).
-
Optimal emulations by butterfly-like networks,
JACM 43 (1996), 293--330,
(with S. Bhatt, Jia-Wei Hong, F. T. Leighton, Bojana Obrenic, A. L. Rosenberg and E.J. Schwabe).
-
On sampling with Markov chains,
Random Structures and Algorithms 9 (1996) 55--77.
(with R. L. Graham and S. -T. Yau).
-
Scheduling tree-dags using FIFO queues: A control-memory tradeoff,
Journal of Parallel and Distributed Computing 33 (1996), 55--68,
(with Sandeep N. Bhatt, Tom Leighton and Arny Rosenberg).
1991-1995
Back to top
-
Salvage embeddings of complete trees,
SIAM J. Discrete Math. 8 (1995), 617--637,
(with S. Bhatt, F. T. Leighton, and A. L. Rosenberg).
-
Routing permutations on graphs via matchings,
SIAM J. Discrete Math. 7 (1994) 513--530,
(with Noga Alon and R. L. Graham).
-
Communication complexity and quasi-randomness,
SIAM J. Discrete Math. 6 (1993), 110--123,
(with Prasad Tetali)
-
Efficient embeddings of trees in hypercubes,
SIAM Journal on Computing 21 (1992), 151--162,
(with S. Bhatt, F. T. Leighton and A. Rosenberg)
-
A note on finding a strict saddlepoint,
Amer. Math. Monthly 98 (1991), 418--419,
(with Daniel Bienstock, Michael Fredman, Alejandro A. Schaffer, Peter W. Shor and Subhash Suri).
-
Improved separators for planar graphs,
Graph Theory, Combinatorics, and Applications, John Wiley and Sons, (1991), 265--270.
-
Regularity lemmas for hypergraphs and quasi-randomness,
Random Structures and Algorithms 2 (1991), 241--252.
1986-1990
Back to top
-
Quasi-random classes of hypergraphs,
Random Structures and Algorithms 1 (1990), 363--382.
Corrigendum.
-
Quasi-random hypergraphs,
Proc. Natl. Acad. Sci. USA 86 (1989), 8175--8177,
Long
version appeared in Random Structures
and Algorithms 1 (1990), 105--124,
(with R.L. Graham).
-
Optical orthogonal codes: design, analysis and applications,
IEEE Trans. on Information Theory 35, No. 3, (1989), 595--604,
(with J. Salehi and V. Wei).
Erratum.
-
Optimal simulations by butterfly networks,
Proc. of the Twentieth Annual ACM Symposium on Theory of Computing, (1988), 192--204,
(with S. N. Bhatt, Jia-Wei Hong, F. T. Leighton and A. L. Rosenberg).
-
Dynamic search in graphs,
Discrete Algorithms and Complexity (1987), 351--387,
(with R. L. Graham and M. Saks).
-
Embedding graphs in books: a layout
problem with applications to VLSI design,
SIAM J. Algebraic Discrete Methods 8 (1987), no. 1, 33--58,
also in
Graph theory with applications
to algorithms and computer science (Kalamazoo, Mich., 1984), 175--188,
Wiley-Intersci. Publ., Wiley, New York, 1985,
(with F.T. Leighton and A.L. Rosenberg).
-
Optimal simulations of tree machines,
27th Annual Symposium on Foundations of Computer Science (1986), 274--282,
(with S. N. Bhatt, F. T. Leighton and A. L. Rosenberg).
-
Minced trees, with applications to fault-tolerant VLSI processor arrays,
Math. Systems Theory 19 (1986), 1--12,
(with A. L. Rosenberg).
-
Partitioning circuits for improved testability,
4th MIT Conf. on Advanced Research in VLSI,
(C. E. Leiserson, ed.), The MIT Press, Cambridge
(1986), 91--106,
(with S. N. Bhatt, A. L. Rosenberg).
1981-1985
Back to top
-
Self-organizing sequential search and Hilbert's inequalities
Proceedings of the Seventeenth Annual
ACM Symposium on Theory of Computing 8 (1985), 217--223,
also in J. Comp. System Sc. 36 (1988), 148--157,
(with D. J. Hajela and P. D. Seymour).
-
Coding strings by pairs of strings,
SIAM J. Algebraic Discrete Methods 6 (1985), no. 3, 445--461,
also in Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory
and computing (Boca Raton, Fla., 1983) Congr. Numer. 39 (1983), 183--191,
(with R.E. Tarjan, W.J. Paul, and R. Reischuk).
-
On the cutwidth and the topological
bandwidth of a tree,
SIAM J. Algebraic Discrete Methods 6 (1985), no. 2, 268--277.
-
Perfect storage representations for families
of data structures,
SIAM J. Algebraic Discrete Methods 4 (1983), no. 4, 548--565,
(with A.L. Rosenberg and Lawrence Snyder).
-
On packing two-dimensional bins,
SIAM J. Algebraic Discrete Methods 3 (1982), no. 1, 66--76,
(with M. R. Garey and D. S. Johnson).
-
On the decompositions of graphs,
SIAM J. Alg. Disc. Methods 2 (1981), 1--12.
1975-1980
Back to top
1973-1975
Back to top
|