Premium
On testing isomorphism of permutation graphs
Author(s) -
Colbourn Charles J.
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110103
Subject(s) - graph isomorphism , combinatorics , mathematics , permutation graph , isomorphism (crystallography) , discrete mathematics , chordal graph , comparability , induced subgraph isomorphism problem , graph , line graph , voltage graph , crystallography , chemistry , crystal structure
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom