A Class of Balanced Matrices Arising from Location Problems

DOI10.1137/0604036zbMath0557.05021OpenAlexW2050038504MaRDI QIDQ3222208

Arie Tamir

Publication date: 1983

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0604036

zbMATH Keywords

triangulated graphsintersection graphssubtreesbalanced incidence matricesneighbourhood subtree

Mathematics Subject Classification ID

Trees (05C05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Related Items

NeST graphs, Reliability, covering and balanced matrices, A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices, Totally balanced and totally unimodular matrices defined by center location problems, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Recognition of linear and star variants of leaf powers is in P, Balanced matrices, On locating new facilities in a competitive environment, Locational analysis, Location routing problems on trees, Competitive location in the plane, Rooted directed path graphs are leaf powers, Perfect, ideal and balanced matrices, Balanced Cayley graphs and balanced planar graphs, Exact leaf powers, Neighborhood subtree tolerance graphs, Optimisation and hypergraph theory, Totally-Balanced and Greedy Matrices

Cites Work

• Unnamed Item
• Unnamed Item
• A characterisation of rigid circuit graphs
• Normal hypergraphs and the perfect graph conjecture
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Polynomially bounded algorithms for locatingp-centers on a tree
• Perfect zero–one matrices
• Balanced matrices
• Blocking and anti-blocking pairs of polyhedra