On the coding of ordered graphs
This paper describes a coding procedure for ordered graphs. Using this procedure it is shown that the ordered graph isomorphism problem can be optimally solved in quadratic time. If \(X\) is a set of graphs and \(Y\) the set of strings of symbols from some alphabet, then a coding procedure is a mapping \(c:X\to Y\) such that two graphs in \(X\) map into the same string of \(Y\) if and only if they are isomorphic. An ordered graph is an undirected graph \(G=(V,E)\) where for each vertex \(v\in V\) there is a cyclic ordering \(L(v)\) of the neighbors of \(v\). Two ordered graphs are ordered isomorphic if there exists a bijection between their vertex sets that preserves both adjacency and order. This paper describes a coding procedure for ordered graphs. Given an ordered graph with \(m\) edges, the procedure produces a total of \(2m\) subcodes (two per edge) where each subcode is a string of \(2m\) natural numbers. The lexicographically least of these is then chosen as the code for the graph. It is shown that two graphs are ordered isomorphic if and only if they have the same code. An \(O(m^2)\) algorithm to determine whether two ordered graphs are ordered isomorphic is given. The authors provide experimental evidence which underlines the efficiency of their approach.
- A V log V algorithm for isomorphism of triconnected planar graphs
- An Algorithm for Subgraph Isomorphism
- Further annotated bibliography on the isomorphism disease
- Graph isomorphism is in the low hierarchy
- scientific article; zbMATH DE number 3575612 (Why is no real title available?)
- scientific article; zbMATH DE number 3390780 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- The graph isomorphism disease
This page was built for publication: On the coding of ordered graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1266307)
