On the coding of ordered graphs
type: Item
instance of: scholarly article
title: On the coding of ordered graphs
zbMATH Open document ID: 0912.05047
DOI: 10.1007/BF02684448
published in: Computing
publication date: 1999-05-09T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1199876
zbMATH Keywords: coding
zbMATH Keywords: ordered graph
zbMATH Keywords: isomorphism
author: Xiaoyi Jiang
author: Horst Bunke
reviewed by: Robert R. Molina
MaRDI profile type: Publication
cites work: Further annotated bibliography on the isomorphism disease
cites work: A V log V algorithm for isomorphism of triconnected planar graphs
cites work: Q4148000
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Q5659553
cites work: The graph isomorphism disease
cites work: Graph isomorphism is in the low hierarchy
cites work: An Algorithm for Subgraph Isomorphism
description: scientific article; zbMATH DE number 1199876