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 (75)
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
This page was built for publication: Doubly Lexical Orderings of Matrices
