Doubly lexical ordering of dense 0--1 matrices
From MaRDI portal
Publication:2366069
DOI10.1016/0020-0190(93)90209-RzbMath0771.68068MaRDI QIDQ2366069
Publication date: 29 June 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
An optimal algorithm to recognize Robinsonian dissimilarities ⋮ An approximation algorithm for clustering graphs with dominating diametral path ⋮ COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS ⋮ The recognition of geodetically connected graphs ⋮ Solving the all-pairs-shortest-length problem on chordal bipartite graphs ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Unified all-pairs shortest path algorithms in the chordal hierarchy ⋮ On recognition of threshold tolerance graphs and their complements ⋮ Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs ⋮ Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ Possible numbers of \(x\)'s in an \(\{x, y\}\)-matrix with a given rank ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ Finding a sun in building-free graphs ⋮ Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time ⋮ Broadcast domination and multipacking in strongly chordal graphs ⋮ Weighted maximum-clique transversal sets of 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 ⋮ On the complexity of variations of mixed domination on graphs† ⋮ The parallel complexity of elimination ordering procedures ⋮ Doubly-lexical order supports standardisation and recursive partitioning of formal context ⋮ Arboricity, \(h\)-index, and dynamic algorithms ⋮ Variations of maximum-clique transversal sets on graphs ⋮ A new graph parameter to measure linearity ⋮ Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs ⋮ Rainbow domination and related problems on strongly chordal graphs ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ Variations of \(Y\)-dominating functions on graphs ⋮ The Dilworth number of auto-chordal bipartite graphs ⋮ Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph ⋮ Monge and feasibility sequences in general flow problems ⋮ 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 ⋮ Signed and minus clique-transversal functions on graphs ⋮ Signed clique-transversal functions in graphs ⋮ The degree-preserving spanning tree problem in strongly chordal and directed path graphs ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ On the complexity of signed and minus total domination in graphs ⋮ Recognition and drawing of stick graphs ⋮ From a simple elimination ordering to a strong elimination ordering in linear time ⋮ \(k\)-tuple domination in graphs ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Totally balanced dissimilarities ⋮ PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT ⋮ Totally Balanced Formal Context Representation ⋮ 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
Cites Work
