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)

Full work available at URL https://doi.org/10.1016/0196-6774(91)90010-V

zbMATH Keywords

Common CRCW PRAMconsecutive 1's property for rowsconvex bipartite graphsmaximum matching problemNC algorithm

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)

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

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)