Tata Institute of Fundamental Research
An Upper Bound on the Bisection Width of d-Regular Graphs
Student Seminar
Speaker:
Devendra Desai
Rutgers University
Department of Computer Science
110 Frelinghuysen Road
Piscataway, NJ 08854-
Date:
Friday, 12 Aug 2011 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The 'bisection width' of a graph is defined as the minumum number of edges that need to be removed to partition the graph into two equal halves. If the graph is 'sparse', then we don't expect this quantity to be large. In this talk, I will present a result of Noga Alon, which gives an upper bound on the bisection width of any d-regular graph, where the number of vertices is 'much more' than d. Time permitting, I will also discuss some other interesting cut problems and what we know about them.
| Speaker: | Devendra Desai Rutgers University Department of Computer Science 110 Frelinghuysen Road Piscataway, NJ 08854- |
| Date: | Friday, 12 Aug 2011 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The 'bisection width' of a graph is defined as the minumum number of edges that need to be removed to partition the graph into two equal halves. If the graph is 'sparse', then we don't expect this quantity to be large. In this talk, I will present a result of Noga Alon, which gives an upper bound on the bisection width of any d-regular graph, where the number of vertices is 'much more' than d. Time permitting, I will also discuss some other interesting cut problems and what we know about them.