Birds of a Feather Flock Together

Speaker:        Yixin Cao
                Polytechnic University

Title:          "Birds of a Feather Flock Together"

Date:           Thursday, Feb 25

Time:           11:00am - 12 noon

Venue:          Room 3494 (via lift 25/26), HKUST

Abstract:

A simple observation in graphs is that some vertices are ``alike'': A set
of vertices is a module if they have the same neighborhood outside this
set, and they can be treated as a whole for many problems.  A nice theory
has been built on the properties of modules, and in particular, all the
modules of a graph can be represented by a hierarchical tree structure.
This provides a very handy, and sometimes indispensable, tool for solving
a large family of graph problems.  We survey the use of modules in
algorithm design, including both classic results and our recent ones.


More information on the CSE Theory Seminars can be found at
http://cse.hkust.edu.hk/tcsc/seminars.html