Department of Mathematics

Indian Institute Of Technology Madras , Chennai

An Algorithm for a special case of Connected $f$-Factors

Speaker : C S Rahul, CSE, IITM


Abstract :

Given and edge weighted undirected graph $G=(V,E)$ with $|V|=n$, and a function $fV mapsto mathbb{N}$, we consider the problem of finding a connected $f$-factor in $G$. In particular, for each constant $cge 2$, we consider the case when $f(v)ge frac{n}{c}$, for all $v$ in $V$. We characterize the set of graphs that have a connected $f$-factor for $f(v) ge frac{n}{3}$, for every $v$ in $V$, and this gives a polynomial time algorithm for the decision version of the problem. Extending the techniques, we solve the minimization version.

Key Speaker C S Rahul, CSE, IITM
Place Madhava Hall
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None