Characterizations of totally balanced matrices

DOI10.1016/0196-6774(84)90028-2zbMath0551.05026OpenAlexW2083371178MaRDI QIDQ3344216

Martin Farber, Richard P. Anstee

Publication date: 1984

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(84)90028-2

zbMATH Keywords

(0,1)-matrixstrongly chordal graphsbalanced matrices

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (65)

Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Doubly lexical ordering of dense 0--1 matrices ⋮ A polyhedral view to a generalization of multiple domination ⋮ General forbidden configuration theorems ⋮ Convexity in Graphs and Hypergraphs ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Decomposition of wheel-and-parachute-free balanced bipartite graphs ⋮ Totally balanced and totally unimodular matrices defined by center location problems ⋮ Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs ⋮ On hypergraph acyclicity and graph chordality ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ A note on perfectly orderable graphs ⋮ A note on odd/even cycles ⋮ Meyniel weakly triangulated graphs. II: A theorem of Dirac ⋮ A decomposition strategy for the vertex cover problem ⋮ Incidence graphs of biacyclic hypergraphs ⋮ On strictly chordality-\(k\) graphs ⋮ Broadcast domination and multipacking in strongly chordal graphs ⋮ Equivalence between hypergraph convexities ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ Dually chordal graphs ⋮ Optimal design of line replaceable units ⋮ Comparability digraphs: an analogue of comparability graphs ⋮ Computing simple-path convex hulls in hypergraphs ⋮ The multiple domination and limited packing problems in graphs ⋮ Unnamed Item ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Balanced matrices ⋮ Which claw-free graphs are strongly perfect? ⋮ \(L(2,1)\)-labeling of perfect elimination bipartite graphs ⋮ On opposition graphs, coalition graphs, and bipartite permutation graphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ Min-Orderable Digraphs ⋮ Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite 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 ⋮ Classes of bipartite graphs related to chordal graphs ⋮ Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs ⋮ Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph ⋮ Meyniel weakly triangulated graphs. I: Co-perfect orderability ⋮ Structural properties and decomposition of linear balanced matrices ⋮ Which claw-free graphs are perfectly orderable? ⋮ Complexity of distance paired-domination problem in graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ \(k\)-tuple domination in graphs ⋮ Optimisation and hypergraph theory ⋮ Decomposition of balanced matrices ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ A study of algorithms relating distributive lattices, median graphs, and Formal Concept Analysis ⋮ Totally balanced dissimilarities ⋮ Perfect circular arc coloring ⋮ Domination, independent domination, and duality in strongly chordal graphs ⋮ Strong Chordality of Graphs with Possible Loops ⋮ Large Homogeneous Submatrices ⋮ Totally Balanced Formal Context Representation ⋮ On balanced graphs ⋮ Clique graphs and Helly graphs ⋮ The domatic number problem on some perfect graph families ⋮ Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs ⋮ Efficient \((j, k)\)-dominating functions ⋮ A characterization of totally balanced hypergraphs ⋮ Some recent results in the analysis of greedy algorithms for assignment problems

This page was built for publication: Characterizations of totally balanced matrices