Totally-Balanced and Greedy Matrices

DOI10.1137/0606070zbMath0573.05041OpenAlexW1976427966MaRDI QIDQ3691772

M. Sakarovitch, Alan J. Hoffman, Antoon W. J. Kolen

Publication date: 1985

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

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

zbMATH Keywords

totally-balanced matrixgreedy matrixtree location theory

Mathematics Subject Classification ID

Trees (05C05) Integer programming (90C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (83)

Solving the uncapacited plant location problem on trees ⋮ The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs ⋮ Steiner trees, connected domination and strongly chordal graphs ⋮ A general approach to avoiding two by two submatrices ⋮ Doubly lexical ordering of dense 0--1 matrices ⋮ A tight relation between series-parallel graphs and bipartite distance hereditary graphs ⋮ Solving the all-pairs-shortest-length problem on chordal bipartite graphs ⋮ Convexity in Graphs and Hypergraphs ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices ⋮ Decomposition of wheel-and-parachute-free balanced bipartite graphs ⋮ Forbidden submatrices ⋮ Totally balanced and totally unimodular matrices defined by center location problems ⋮ Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs ⋮ The one-dimensional Euclidean domain: finitely many obstructions are not enough ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ A note on perfectly orderable graphs ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ A note on odd/even cycles ⋮ Search-hide games on trees ⋮ Broadcast domination and multipacking in strongly chordal graphs ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ Online clustering with variable sized clusters ⋮ Dually chordal graphs ⋮ Optimal design of line replaceable units ⋮ Comparability digraphs: an analogue of comparability graphs ⋮ The multiple domination and limited packing problems in graphs ⋮ A ranking model for the greedy algorithm and discrete convexity ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Balanced matrices ⋮ Which claw-free graphs are strongly perfect? ⋮ On opposition graphs, coalition graphs, and bipartite permutation graphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ On the complexity of the black-and-white coloring problem on some classes of perfect graphs ⋮ Rainbow domination and related problems on strongly chordal graphs ⋮ Standard graded vertex cover algebras, cycles and leaves ⋮ Storage management of items in two levels of availability ⋮ A characterization of the single-crossing domain ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ Classes of bipartite graphs related to chordal graphs ⋮ Rectangle blanket problem: binary integer linear programming formulation and solution algorithms ⋮ A weighted min-max relation for intervals ⋮ Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph ⋮ NP-hard graph problems and boundary classes of graphs ⋮ How to Secure Matchings against Edge Failures ⋮ Structural properties and decomposition of linear balanced matrices ⋮ Greedy oriented flows ⋮ On complexities of minus domination ⋮ An algorithmic framework for tool switching problems with multiple objectives ⋮ Monge and feasibility sequences in general flow problems ⋮ Which claw-free graphs are perfectly orderable? ⋮ On simple combinatorial optimization problems. A collection of contributions in honour of Jack van Lint ⋮ Complexity of distance paired-domination problem in graphs ⋮ Improved approximations for guarding 1.5-dimensional terrains ⋮ What the transportation problem did for me ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ An efficient algorithm for the uncapacitated facility location problem with totally balanced matrix ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ Koszul multi-Rees algebras of principal \(L\)-Borel ideals ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ \(k\)-tuple domination in graphs ⋮ Induced matchings ⋮ Optimisation and hypergraph theory ⋮ How to Secure Matchings Against Edge Failures ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Boundary Properties of Factorial Classes of Graphs ⋮ Combinatorial optimization models for production scheduling in automated manufacturing systems ⋮ Greedy sets and related problems ⋮ Decomposition of balanced matrices ⋮ Solving covering problems and the uncapacitated plant location problem on trees ⋮ Domination, independent domination, and duality in strongly chordal graphs ⋮ Characterizations of strongly chordal graphs ⋮ Exact Solution of Two Location Problems via Branch-and-Bound ⋮ Strong Chordality of Graphs with Possible Loops ⋮ Large Homogeneous Submatrices ⋮ Location problems ⋮ On Complexities of Minus Domination ⋮ The domatic number problem on some perfect graph families ⋮ A characterization of totally balanced hypergraphs ⋮ Some recent results in the analysis of greedy algorithms for assignment problems ⋮ An efficient algorithm for solving a special class of LP's ⋮ Airline crew scheduling: state-of-the-art

Cites Work

• Characterizations of strongly chordal graphs
• A Class of Balanced Matrices Arising from Location Problems
• Balanced matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Totally-Balanced and Greedy Matrices