Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Efficient parallel algorithms for bipartite permutation graphs
View through CrossRef
AbstractIn this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation graphs. These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation graph; testing isomorphism; finding a Hamiltonian path/cycle; solving a variant of the crossing number problem; and others. All these problems can be solved inO(log2n) time withO(n3) processors on a Common CRCW PRAM. We also show that the minimum fill‐in problem for bipartite permutation graphs can be solved efficiently by a randomized parallel algorithm. ©1993 by John Wiley & Sons, Inc.
Title: Efficient parallel algorithms for bipartite permutation graphs
Description:
AbstractIn this paper, we further study the properties of bipartite permutation graphs.
We give first efficient parallel algorithms for several problems on bipartite permutation graphs.
These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation graph; testing isomorphism; finding a Hamiltonian path/cycle; solving a variant of the crossing number problem; and others.
All these problems can be solved inO(log2n) time withO(n3) processors on a Common CRCW PRAM.
We also show that the minimum fill‐in problem for bipartite permutation graphs can be solved efficiently by a randomized parallel algorithm.
©1993 by John Wiley & Sons, Inc.
Related Results
Complete (2,2) Bipartite Graphs
Complete (2,2) Bipartite Graphs
A bipartite graph G can be treated as a (1,1) bipartite graph in the sense that, no two vertices in the same part are at distance one from each other. A (2,2) bipartite graph is an...
Independent Set in Neutrosophic Graphs
Independent Set in Neutrosophic Graphs
New setting is introduced to study neutrosophic independent number and independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key term to have th...
Failed Independent Number in Neutrosophic Graphs
Failed Independent Number in Neutrosophic Graphs
New setting is introduced to study neutrosophic failed-independent number and failed independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key t...
Fidelity and entanglement of random bipartite pure states: insights and applications
Fidelity and entanglement of random bipartite pure states: insights and applications
Abstract
We investigate the fidelity of Haar random bipartite pure states from a fixed reference quantum state and their bipartite entanglement. By plotting the fide...
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Abstract
Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characteriz...
BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE
BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE
The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjectu...
An efficient permutation approach for SbPN-based symmetric block ciphers
An efficient permutation approach for SbPN-based symmetric block ciphers
AbstractIt is challenging to devise lightweight cryptographic primitives efficient in both hardware and software that can provide an optimum level of security to diverse Internet o...
On Bipartite Distance-Regular Cayley Graphs with Small Diameter
On Bipartite Distance-Regular Cayley Graphs with Small Diameter
We study bipartite distance-regular Cayley graphs with diameter three or four. We give sufficient conditions under which a bipartite Cayley graph can be constructed on the semidire...