RUTCOR Colloquia - June 23, 2005
Speaker: Bruno Simeone
Affiliation: La Sapienza University - Rome, Italy
Title: Tree partitioning, weakly triangulated graphs, and maximum closures
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
This talk deals with the following graph partitioning problem. Given a set S of
p nodes, called centers, and its complement V-S, whose n nodes are called units,
the goal is to find a partition of the set of nodes into connected components
containing only one center each, so as to minimize the total assignment cost of
units to centers. This problem is known to be NP-hard in general graphs, and it
is shown here to remain such even if the assignment cost is monotonic on
geodesics and the graph is bipartite. Therefore, we look at trees to derive
polynomial time algorithms. Two integer programming formulations of the
problem are provided. We also give an alternative formulation as a weighted
vertex packing problem on a graph which is shown to be weakly triangulated,
whence a polynomial algorithm ensues. Moreover, we develop a faster
O(n2p) dynamic programming algorithm, whose recursion is based on
solving sequences of minimum weight closure problems.
Joint work with Nicola Apollonio, Isabella Lari, Justo Puerto, and Federica
Ricca
Back to Seminars Page.
Back to RUTCOR homepage.
| 
