On Bisecting Random Graphs
A bisection of a graph with an even number of vertices is a partition of the vertex set into two disjoint sets of equal size. Given a bisection, the number of edges having one end in each of the two subsets of the bisection is called the size of the bisection. The bisection size of a graph is the m...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149565 |
| _version_ | 1811078239609683968 |
|---|---|
| author | Bui, Thang Nguyen |
| author2 | Rivest, Ronald L. |
| author_facet | Rivest, Ronald L. Bui, Thang Nguyen |
| author_sort | Bui, Thang Nguyen |
| collection | MIT |
| description | A bisection of a graph with an even number of vertices is a partition of the vertex set into two disjoint sets of equal size. Given a bisection, the number of edges having one end in each of the two subsets of the bisection is called the size of the bisection. The bisection size of a graph is the minimum size of all possible bisections of the graph. |
| first_indexed | 2024-09-23T10:56:19Z |
| id | mit-1721.1/149565 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:56:19Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1495652023-03-30T03:57:53Z On Bisecting Random Graphs Bui, Thang Nguyen Rivest, Ronald L. A bisection of a graph with an even number of vertices is a partition of the vertex set into two disjoint sets of equal size. Given a bisection, the number of edges having one end in each of the two subsets of the bisection is called the size of the bisection. The bisection size of a graph is the minimum size of all possible bisections of the graph. 2023-03-29T15:07:16Z 2023-03-29T15:07:16Z 1983-03 https://hdl.handle.net/1721.1/149565 9523546 MIT-LCS-TR-287 application/pdf |
| spellingShingle | Bui, Thang Nguyen On Bisecting Random Graphs |
| title | On Bisecting Random Graphs |
| title_full | On Bisecting Random Graphs |
| title_fullStr | On Bisecting Random Graphs |
| title_full_unstemmed | On Bisecting Random Graphs |
| title_short | On Bisecting Random Graphs |
| title_sort | on bisecting random graphs |
| url | https://hdl.handle.net/1721.1/149565 |
| work_keys_str_mv | AT buithangnguyen onbisectingrandomgraphs |