zbMATH — the first resource for mathematics

Doubly lexical ordering of dense 0–1 matrices. (English) Zbl 0771.68068
Summary: We present an algorithm for the doubly lexical ordering problem on a 0-1 \(i\) by \(j\) matrix which runs in \(O(ij)\) time. This improves the time bounds for determining whether a dense \(0-1\) matrix is totally balanced, and determining whether a dense graph is strongly chordal or chordal bipartite.

68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Anstee, R.P.; Farber, M., Characterizations of totally balanced matrices, J. algorithms, 5, 215-230, (1984) · Zbl 0551.05026
[2] Eschen, E.M.; Spinrad, J.P., An O(n2) algorithm for circular-arc graph recognition, Proc. 4th ann. ACM-SIAM symp. on discrete algorithms, (1993), to appear · Zbl 0801.68128
[3] Fagin, R., Degrees of acyclicity for hypergraphs and relational database schemes, J. ACM, 30, 514-550, (1983) · Zbl 0624.68088
[4] Farber, M., Characterizations of strongly chordal graphs, Discrete math., 43, 173-189, (1983) · Zbl 0514.05048
[5] Hoffman, A.J.; Kolen, A.W.J.; Sakarovitch, M., Totally balanced and greedy matrices, SIAM J. algebraic discrete methods, 6, 721-730, (1985) · Zbl 0573.05041
[6] Lubiw, A., Doubly lexical orderings of matrices, SIAM J. comput., 16, 854-879, (1987) · Zbl 0622.05045
[7] Ma, T.; Spinrad, J., An O(n2) time algorithm for the 2-chain cover problem and related problems, Proc. 2nd ann. ACM - SIAM symp. on discrete algorithms, 363-372, (1991) · Zbl 0800.68606
[8] Paige, R.; Tarjan, R.E., Three partition refinement algorithms, SIAM J. comput., 16, 973-989, (1987) · Zbl 0654.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.