Program > By author > Nguyen Viet Hung

A star is a graph in which some vertex is incident with every edge of the graph, i.e. a graph of diameter at most 2.
A star forest is a graph in which each connected component is a star.
 Given a connected graph $G$ in which
the edges may be weighted positively. A spanning star forest
of $G$ is a subgraph of $G$ which is a star forest spanning the vertices of $G$. The size of a spanning star forest
$F$ of $G$ is defined to be the number of edges of $F$ if $G$ is unweighted and the total weight of all edges of $F$ if
$G$ is weighted. We are interested in the problem of finding a Maximum Weight spanning Star Forest (MWSFP) in $G$. In \cite{CTNguyen}, the authors introduced the MWSFP and
proved its NP-hardness. They also gave a polynomial time algorithm for the MWSF problem when $G$ is a tree.\\
 In this paper, we present a polyhedral investigation of the maximal weight spanning star forest problem. In particular, we define two new classes of facet-defining inequalities that
 give complete linear programming formulations of the problem when $G$ is either a tree or a cycle. We also give a polynomial time combinatorial algorithm that solves the
 MSWF problem when $G$ is a cycle.