Bipartite permutation graphs (Q1092931)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Bipartite permutation graphs |
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
