On testing isomorphism of permutation graphs

DOI10.1002/NET.3230110103zbMath0459.68031OpenAlexW2111070448MaRDI QIDQ3910010

Charles J. Colbourn

Publication date: 1981

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230110103

zbMATH Keywords

polynomial time algorithmcomparability graphs of two-dimensional partial orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10)

Related Items (35)

Bipartite permutation graphs ⋮ Isomorphism of chordal (6, 3) graphs ⋮ Isomorphism testing for \(T\)-graphs in FPT ⋮ Perfect matching cuts partitioning a graph into complementary subgraphs ⋮ Strong tree-cographs are Birkhoff graphs ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ Polynomial Equations over Finite, Discrete-Time Dynamical Systems ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Polynomial time algorithms for variants of graph matching on partial \(k\)-trees ⋮ On the isomorphism of graphs having some eigenvalues of moderate multiplicity ⋮ A compact data structure and parallel algorithms for permutation graphs ⋮ Cleaning interval graphs ⋮ Random generation and enumeration of bipartite permutation graphs ⋮ Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs ⋮ Succinct permutation graphs ⋮ Directed path graph isomorphism ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Finding a maximum independent set in a permutation graph ⋮ Subgraph isomorphism in graph classes ⋮ Graphs whose complement and square are isomorphic ⋮ A note on compact graphs ⋮ The isomorphism problem for classes of graphs closed under contraction ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ VF2++ -- an improved subgraph isomorphism algorithm ⋮ \(P_ 4\)-trees and substitution decomposition ⋮ Partitioning a graph into complementary subgraphs ⋮ Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs ⋮ Simple Geometrical Intersection Graphs ⋮ Graph isomorphism restricted by lists ⋮ A vertex ordering characterization of simple-triangle graphs ⋮ The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw ⋮ Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs ⋮ Modular decomposition and transitive orientation ⋮ Graph isomorphism problem

Cites Work

• Planar Lattices
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: On testing isomorphism of permutation graphs