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.
- Standort
-
Deutsche Nationalbibliothek Frankfurt am Main
- Umfang
-
Online-Ressource
- Sprache
-
Englisch
- Erschienen in
-
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)
- Urheber
-
Čibej, Uroš
Mihelič, Jurij
- DOI
-
10.1515/comp-2020-0186
- URN
-
urn:nbn:de:101:1-2410301457278.637723606783
- Rechteinformation
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Letzte Aktualisierung
-
15.08.2025, 07:22 MESZ
Datenpartner
Deutsche Nationalbibliothek. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Beteiligte
- Čibej, Uroš
- Mihelič, Jurij
Ähnliche Objekte (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