Compression of vertex transitive graphs

Litow, Bruce, Deo, Narsingh, and Cami, Aurel (2004) Compression of vertex transitive graphs. Congressus Numerantium, 167. pp. 161-173.

[img] PDF (Published Version)
Restricted to Repository staff only

View at Publisher Website: http://www.cs.ucf.edu/csdept/faculty/deo...

Abstract

We consider the lossless compression of vertex transitive graphs. An undirected graph G = (V, E) is called vertex transitive if for every pair of vertices x, y ∈ V , there is an automorphism σ of G, such that σ(x) = y. A result due to Sabidussi, guarantees that for every vertex transitive graph G there exists a graph mG (m is a positive integer) which is a Cayley graph. We propose as the compressed form of G a finite presentation (X, R) , where (X, R) presents the group Γ corresponding to such a Cayley graph mG. On a conjecture, we demonstrate that for a large subfamily of vertex transitive graphs, the original graph G can be completely reconstructed from its compressed representation.

Item ID: 6117
Item Type: Article (Refereed Research - C1)
Keywords: compression; vertex transitive graphs
Related URLs:
ISSN: 0384-9864
Date Deposited: 08 Jan 2010 02:04
FoR Codes: 08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080201 Analysis of Algorithms and Complexity @ 100%
SEO Codes: 89 INFORMATION AND COMMUNICATION SERVICES > 8999 Other Information and Communication Services > 899999 Information and Communication Services not elsewhere classified @ 100%
Downloads: Total: 1
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page