Doubly Lexical Orderings of Matrices
From MaRDI portal
Publication:3758873
DOI10.1137/0216057zbMath0622.05045OpenAlexW1968148694MaRDI QIDQ3758873
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216057
chordal graphstotally balanced matriceslexical orderingacyclic hypergraphsacyclic data basesDoubly lexical orderingssubtree matrices
Related Items
A general approach to avoiding two by two submatrices, Doubly lexical ordering of dense 0--1 matrices, Characterizations of two classes of digraphs, Solving the all-pairs-shortest-length problem on chordal bipartite graphs, An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs, Permuting matrices to avoid forbidden submatrices, Bipartite completion of colored graphs avoiding chordless cycles of given lengths, Generating effective symmetry-breaking predicates for search problems, Unified all-pairs shortest path algorithms in the chordal hierarchy, Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs, Transversal partitioning in balanced hypergraphs, A note on perfectly orderable graphs, A note on odd/even cycles, Meyniel weakly triangulated graphs. II: A theorem of Dirac, Recognizing single-peaked preferences on a tree, On orthogonal ray graphs, Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem, Incidence graphs of biacyclic hypergraphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Even pairs in claw-free perfect graphs, Broadcast domination and multipacking in strongly chordal graphs, Maximum vertex-weighted matching in strongly chordal graphs, A linear-time algorithm for semitotal domination in strongly chordal graphs, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, The parallel complexity of elimination ordering procedures, Dually chordal graphs, On minimally non-firm binary matrices, A good characterization of squares of strongly chordal split graphs, The multiple domination and limited packing problems in graphs, Unnamed Item, Strong Cocomparability Graphs and Slash-Free Orderings of Matrices, Balanced matrices, A new graph parameter to measure linearity, 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, Rainbow domination and related problems on strongly chordal graphs, Standard graded vertex cover algebras, cycles and leaves, Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs, Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs, A weighted min-max relation for intervals, The Dilworth number of auto-chordal bipartite graphs, Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs, Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph, The matrix taxonomy of finitely complete categories, Monge and feasibility sequences in general flow problems, Which claw-free graphs are perfectly orderable?, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Complexity of distance paired-domination problem in graphs, Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation, A linear‐time algorithm for broadcast domination in a tree, A linear-time algorithm for paired-domination problem in strongly chordal graphs, Recognition and drawing of stick graphs, Quasimonotone graphs, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Graph classes and the switch Markov chain for matchings, From a simple elimination ordering to a strong elimination ordering in linear time, \(k\)-tuple domination in graphs, Hardness and structural results for half-squares of restricted tree convex bipartite graphs, Broadcast Domination in Graphs, Improved algorithms for the multicut and multiflow problems in rooted trees, Bichromatic \(P_{4}\)-composition schemes for perfect orderability, Simplicial powers of graphs, Totally balanced dissimilarities, Perfect circular arc coloring, A characterization of strongly chordal graphs, Simplicial Powers of Graphs, Strong Chordality of Graphs with Possible Loops, Large Homogeneous Submatrices, Additive sparse spanners for graphs with bounded length of largest induced cycle, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, The domatic number problem on some perfect graph families, Broadcast domination and multipacking: bounds and the integrality gap, Dominating cliques in chordal graphs
