Claudson F. Bornstein, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman
wraparound. The former result is surprising, since it contradicts the prior "folklore " belief that the bisection width is n. We also show that every set of k nodes has at least k 2 log k...
Claudson F. Bornstein, Santosh Vempala
Abstract. We introduce ow metrics as a relaxation of path metrics (i.e. linear orderings). They are dened by polynomial-sized linear programs and have interesting properties including spreading. We...
Tradeoffs Between Parallelism and Fill in Nested Dissection (1999)
Claudson F. Bornstein, Bruce M. Maggs, Gary L. Miller
In this paper we demonstrate that tradeoffs can be made between parallelism and fill in nested dissection algorithms for Gaussian elimination, both in theory and in practice. We present a new...
On the Bisection Width and Expansion of Butterfly Networks (1997)
Claudson F. Bornstein, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman, Tal Yatzkar
This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. We show that the bisection width of an n-input butterfly network is 2( p 2...
On Clique Convergent Graphs (1995)
Claudson F. Bornstein, Jayme L. Szwarcfiter, Caixa Postal
A graph G is convergent when there is some finite integer n 0, such that the n-th iterated clique graph K n (G) has only one vertex. The smallest such n is the index of G. The Helly defect of a...
Clique Graphs Of Chordal And Path Graphs (1994)
Jayme L. Szwarcfiter, Claudson F. Bornstein, F. Bornstein
. Clique graphs of chordal and path graphs are characterized. A special class of graphs named expanded trees is discussed. It consists of a subclass of disk-Helly graphs. It is shown that the clique...