Parallel recognition of the consecutive ones property with applications
From MaRDI portal
Publication:3348413
DOI10.1016/0196-6774(91)90010-VzbMath0726.68034MaRDI QIDQ3348413
Publication date: 1991
Published in: Journal of Algorithms (Search for Journal in Brave)
convex bipartite graphsmaximum matching problemNC algorithmCommon CRCW PRAMconsecutive 1's property for rows
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distributed algorithms (68W15)
Related Items
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace, Optimal computation of shortest paths on doubly convex bipartite graphs, Graph isomorphism and identification matrices: Sequential algorithms, Efficient parallel algorithms for doubly convex-bipartite graphs, Efficient parallel recognition of some circular arc graphs. II, Circular-arc hypergraphs: rigidity via connectedness, 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, A type of algebraic structure related to sets of intervals, On the isomorphism problem for Helly circular-arc graphs
