A Linear Algorithm for Universal Minimal Dominating Functions in Trees

Abstract

A $dominatingfunction$ is a feasible solution to the LP relaxation of the minimum dominating set $0-1$ integer program. A minimal dominating function (MDF) g is called universal if every convex combination of g and any other MDF is also a MDF. The problem of finding a universal MDF in a tree $T$ can also be described by a linear program. This paper describes a linear time algorithm that finds a universal MDF in $T$, if one exists.