Graph automorphisms for compression
| Autor: | Jurij Mihelič, Uros Cibej |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
General Computer Science Computer science graph classes QA75.5-76.95 02 engineering and technology Automorphism Electronic computers. Computer science 020204 information systems 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) 020201 artificial intelligence & image processing compression algorithms graph automorphisms Data compression |
| Zdroj: | Open Computer Science, Vol 11, Iss 1, Pp 51-59 (2020) |
| ISSN: | 2299-1093 |
| DOI: | 10.1515/comp-2020-0186 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|