דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Approximate Hypergraph Partitioning and Applications
event speaker icon
אסף שפירא
event date icon
יום ראשון, 30.12.2007, 10:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
I will describe an O(n) time algorithmic version of Szemerdi's regularity lemma. Unlike all the previous approaches for this problem, which proved the lemma "algorithmically", and only guaranteed to find partitions of tower-size, our algorithm will find a small regular partition in the graph in the case that one exists. The algorithm can be extended to an O(n) time algorithmic version of the hypergraph regularity lemma for k-uniform hypergraphs, improving over the previous O(n^{2k-1}) algorithms.

The main tool we develop for the above algorithms is an algorithm for finding approximate partitions of hypergraphs, which significantly generalizes an algorithm of Goldreich-Goldwasser-Ron for finding approximate partitions of graphs.

Joint work with Eldar Fischer and Arie Matsliach
[בחזרה לאינדקס האירועים]