Totally balanced and totally unimodular matrices defined by center location problems (Q1104945)

Let \(T=(V,E)\) be an undirected tree with positive edge lengths. Let S be a subset of V with \(| S| =k\). For each vertex v let \(d^ v_ 1\leq...\leq d^ v_ k\) be the sorted sequence of distances from v to the k vertices in S. For \(i=1,...,k\), let S(v,i) denote the vertex set of the minimal subtree containing v and the vertices of S whose distance from v is at most \(d^ v_ i\). For \(r>0\) let N(v,r) denote the set of vertices in V whose distance from v is at most r. We prove that the collection of all subsets \(\{\) S(v,i)\(\cap N(v,r)\}\), with v in V, \(i=1,...,k\), and \(d^ v_{i-1}\leq r\leq d^ v_ i\), \((d^ v_ 0=0)\), is totally balanced. We also show that the subcollection of all subsets \(\{\) S(v,1)\(\}\) with v i V is totally unimodular. These results extend and unify some previous results on collections of subtrees of a tree, and they imply the existence of polynomial algorithms for several location models on trees. Finally we discuss extensions of the above results to bitrees and strongly chordal graphs.