On testing isomorphism of permutation graphs

DOI10.1002/NET.3230110103MaRDI QIDQ3910010zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3407692 (Why is no real title available?)
• Graph theory with applications
• Planar Lattices
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(35)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3910010)