Signatures of Extremal 2-Unifrom Hypergraphs

Storing hypergraphs in computer memory is rather inefficient, since the main storage method is an incidence matrix or a list of hyper edges. For n -vertex k -uniform hypergraphs (UHs), it is possible to specify an adjacency matrix but its volume is n k . For extremal UHs, it becomes possible to use...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer & systems sciences international 2021-11, Vol.60 (6), p.904-912
Main Authors: Goltsova, T. Yu, Egorova, E. K., Mokryakov, A. V., Tsurkov, V. I.
Format: Article
Language:English
Subjects:
Algorithms
Computer Methods
Control
Engineering
Graph theory
Graphs
Mechatronics
Robotics
Storage
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Storing hypergraphs in computer memory is rather inefficient, since the main storage method is an incidence matrix or a list of hyper edges. For n -vertex k -uniform hypergraphs (UHs), it is possible to specify an adjacency matrix but its volume is n k . For extremal UHs, it becomes possible to use the base in the form of a storage object; it takes up less space in memory than a list of hyper edges, but it is not always convenient from a practical point of view. Here we consider a new concept: the signature of an extremal 2-UH, which is a nonnegative integer and uniquely characterizes the hypergraph. For this representation, algorithms are described for constructing an extremal 2-UH in the form of an adjacency matrix or base from a signature. Algorithms for obtaining a signature from an arbitrary adjacency matrix or base of an extremal 2-UH are also presented.
ISSN:1064-2307
1555-6530
DOI:10.1134/S1064230721060095