Totally balanced and totally unimodular matrices defined by center location problems

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Totally balanced and totally unimodular matrices defined by center location problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104945)