Bipartite permutation graphs (Q1092931)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Bipartite permutation graphs |
scientific article |
Statements
Bipartite permutation graphs (English)
0 references
1987
0 references
It is shown that bipartite permutation graphs have good algorithmic properties in contrast to general bipartite or permutation graphs. Two characterizations of these graphs are presented which lead to a linear time recognition algorithm and also to polynomial algorithms for Hamiltonian problems, a variant of the crossing number problem and the minimum fill-in problem on these graphs.
0 references
bipartite graph
0 references
Hamiltonian cycle
0 references
permutation graphs
0 references
crossing number
0 references
0 references
0 references
