Abstract
A polynomial time algorithm for testing isomorphism of permutation graphs (comparability graphs of 2‐dimensional partial orders) is described. It operates by performing two types of simplifying transformations on the graph; the contraction of duplicate vertices and the contraction of uniquely orientable induced subgraphs.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 13-21 |
| Number of pages | 9 |
| Journal | Networks |
| Volume | 11 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1981 |
| Externally published | Yes |
ASJC Scopus subject areas
- Software
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications