Graph automorphisms for compression
Abstract: Detecting automorphisms is a natural way to identify redundant information presented in structured data. When such redundancies are detected they can be used for data compression. In this paper we explore two different classes of graphs to capture this intuitive property of automorphisms. Symmetry-compressible graphs are the first class which introduces the basic concepts but use only global symmetries for the compression. In order for this concept to be more practical, we need to use local symmetries. Thus, we extend the basic graph class with Near Symmetry compressible graphs. Furthermore, we develop two algorithms that can be used to compress practical instances and empirically evaluate them on a set of realistic graphs.
- Location
-
Deutsche Nationalbibliothek Frankfurt am Main
- Extent
-
Online-Ressource
- Language
-
Englisch
- Bibliographic citation
-
Graph automorphisms for compression ; volume:11 ; number:1 ; year:2020 ; pages:51-59 ; extent:9
Open computer science ; 11, Heft 1 (2020), 51-59 (gesamt 9)
- Creator
-
Čibej, Uroš
Mihelič, Jurij
- DOI
-
10.1515/comp-2020-0186
- URN
-
urn:nbn:de:101:1-2410301457278.637723606783
- Rights
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Last update
-
15.08.2025, 7:22 AM CEST
Data provider
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Associated
- Čibej, Uroš
- Mihelič, Jurij
Other Objects (12)
Distinguishing vertices of a graph: automorphisms and palettes
Cubic Vertex-Transitive Graphs Admitting Automorphisms of Large Order
Graph Compression for Adjacency-Matrix Multiplication
LINE GRAPHS, THEIR DESARGUESIAN CLOSURES, AND CORRESPONDING GROUPS OF AUTOMORPHISMS
Automorphisms of Curves
Automorphisms of buildings
Compression algorithm for colored de Bruijn graphs
A Riemann-Roch theory for sublattices of the root lattice An, graph automorphisms and counting cycles in graphs
Automorphisms of Enriques Surfaces
Correction to: Graph Compression for Adjacency-Matrix Multiplication
GraphZIP: a clique-based sparse graph compression method
Comparing biological networks via graph compression
Distinguishing vertices of a graph: automorphisms and palettes
Cubic Vertex-Transitive Graphs Admitting Automorphisms of Large Order
Graph Compression for Adjacency-Matrix Multiplication
LINE GRAPHS, THEIR DESARGUESIAN CLOSURES, AND CORRESPONDING GROUPS OF AUTOMORPHISMS
Automorphisms of Curves
Automorphisms of buildings
Compression algorithm for colored de Bruijn graphs
A Riemann-Roch theory for sublattices of the root lattice An, graph automorphisms and counting cycles in graphs
Automorphisms of Enriques Surfaces
Correction to: Graph Compression for Adjacency-Matrix Multiplication
GraphZIP: a clique-based sparse graph compression method
Comparing biological networks via graph compression
Distinguishing vertices of a graph: automorphisms and palettes
Cubic Vertex-Transitive Graphs Admitting Automorphisms of Large Order
Graph Compression for Adjacency-Matrix Multiplication
LINE GRAPHS, THEIR DESARGUESIAN CLOSURES, AND CORRESPONDING GROUPS OF AUTOMORPHISMS
Automorphisms of Curves
Automorphisms of buildings
Compression algorithm for colored de Bruijn graphs
A Riemann-Roch theory for sublattices of the root lattice An, graph automorphisms and counting cycles in graphs
Automorphisms of Enriques Surfaces
Correction to: Graph Compression for Adjacency-Matrix Multiplication
GraphZIP: a clique-based sparse graph compression method