.png){kind=icon}
Return
.png){kind=icon}
.png){kind=icon}
Abstract
En 中文
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 is property, and more efficiently in parallel ii at least one matrix satisfies the consecutive Is property. Graphs which have identification matrices satisfying the consecutive Is 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.
Keywords:
consecutive and circular is properties
graph isomorphism testing
identification matrices
parallel algorithms
PRAM
time and processor requirements
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
Organization
No organization information available
Cited Papers
.png){kind=icon}
Share.png){kind=icon}
SaveShareSaveShareSaveCharacterization of the quinones in purple sulfur bacterium Thermochromatium tepidum.png)
FEBS Letters.png)
OAAI
FEBS LettersIF0
OAAIShareSave
ShareSaveShareSaveShareSaveShareSave
View more