Parallel recognition of the consecutive ones property with applications

DOI10.1016/0196-6774(91)90010-VMaRDI QIDQ3348413zbMATH OpenFDO

Authors Lin Chen, Yaacov Yesha

Publication date 1991

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

zbMATH Keywords

convex bipartite graphsmaximum matching problemNC algorithmCommon CRCW PRAMconsecutive 1's property for rows

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• On testing consecutive-ones property in parallel
• scientific article; zbMATH DE number 5606342
• scientific article; zbMATH DE number 3848609
• Tractability results for the consecutive-ones property with multiplicity
• A certifying algorithm for the consecutive-ones property
• On the consecutive ones property
• Towards the parallel repetition conjecture
• scientific article; zbMATH DE number 1696653
• scientific article; zbMATH DE number 1594515
• Parallel enumeration of degree sequences

Cited in

(15)

• scientific article; zbMATH DE number 5606342 (Why is no real title available?)
• A type of algebraic structure related to sets of intervals
• Efficient parallel algorithms for doubly convex-bipartite graphs
• Efficient parallel recognition of some circular arc graphs. I
• A selected tour of the theory of identification matrices
• scientific article; zbMATH DE number 3860441 (Why is no real title available?)
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Graph isomorphism and identification matrices: Sequential algorithms
• On the complexity of the k-chain subgraph cover problem
• On testing consecutive-ones property in parallel
• Circular-arc hypergraphs: rigidity via connectedness
• Optimal computation of shortest paths on doubly convex bipartite graphs
• Efficient parallel recognition of some circular arc graphs. II
• On the isomorphism problem for Helly circular-arc graphs
• On the gapped consecutive-ones property

This page was built for publication: Parallel recognition of the consecutive ones property with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3348413)