Michael R. Capalbo

According to our database, Michael R. Capalbo authored at least 14 papers between 1999 and 2010.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2010

Explicit sparse almost-universal graphs for G(n, k/n).

Michael R. Capalbo

Random Struct. Algorithms, 2010

2008

Optimal universal graphs with deterministic embedding.

Noga Alon, Michael R. Capalbo

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

Sparse universal graphs for bounded-degree graphs.

Noga Alon, Michael R. Capalbo

Random Struct. Algorithms, 2007

Finding Disjoint Paths in Expanders Deterministically and Online.

Noga Alon, Michael R. Capalbo

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2005

Explicit Bounded-Degree Unique-Neighbor Concentrators.

Michael R. Capalbo

Comb., 2005

2003

An Explicit Construction of Lower-Diameter Cubic Graphs.

Michael R. Capalbo

SIAM J. Discret. Math., 2003

Smaller Explicit Superconcentrators.

Noga Alon, Michael R. Capalbo

Internet Math., 2003

2002

Small Universal Graphs for Bounded-Degree Planar Graphs.

Michael R. Capalbo

Comb., 2002

Randomness conductors and constant-degree lossless expanders.

Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Explicit Unique-Neighbor Expanders.

Noga Alon, Michael R. Capalbo

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Near-optimum Universal Graphs for Graphs with Bounded Degrees.

Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski, Endre Szemerédi

Proceedings of the Approximation, 2001

2000

Universality and Tolerance.

Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski, Endre Szemerédi

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Small Universal Graphs.

Michael R. Capalbo, S. Rao Kosaraju

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

A Small Universal Graph for Bounded-degree Planar Graphs.

Michael R. Capalbo

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999