IEEE Transactions on Parallel and Distributed Systems · 1996 · 26 citations · 22 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisData ParallelismGraph AlgorithmsGraph TheoryMatrix ComputationGraph IsomorphismGraph MatchingIdentificationParallel Graph AlgorithmsSubgraph Isomorphism
In this paper, we explore some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a famous open problem. We show that, given two graphs in the form of a certain identification matrix, isomorphism can be tested efficiently in parallel if at least one matrix satisfies the circular 1s property, and more efficiently in parallel if at least one matrix satisfies the consecutive 1s property. Graphs which have identification matrices satisfying the consecutive 1s property include, among others, proper interval graphs and doubly convex bipartite graphs. The result presented here substantially broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms.
22
Incidence matrices and interval graphs
D. R. Fulkerson, Oliver Gross · Pacific Journal of Mathematics · 1965 · 1.3K citations · Full text
An Efficient Parallel Biconnectivity Algorithm
Robert E. Tarjan, Uzi Vishkin · SIAM Journal on Computing · 1985 · 526 citations