Hypergraph recovery algorithms from a given vector of vertex degrees

Methods of obtaining certain classes of hypergraphs from a given integer vector of vertex degrees are considered. These classes are as follows: hyperedges with unit weight incident upon k vertices; hyperedges with unit weight incident upon k vertices in the case when the vertices may be non-unique;...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer & systems sciences international 2014-07, Vol.53 (4), p.511-516
Main Authors: Kostyanoi, D. S., Mokryakov, A. V., Tsurkov, V. I.
Format: Article
Language:English
Subjects:
Algorithms
Computer Methods
Construction
Control
Engineering
Graphs
Integers
Mathematical analysis
Mechatronics
Recovery
Robotics
Studies
Vector space
Vectors (mathematics)
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:Methods of obtaining certain classes of hypergraphs from a given integer vector of vertex degrees are considered. These classes are as follows: hyperedges with unit weight incident upon k vertices; hyperedges with unit weight incident upon k vertices in the case when the vertices may be non-unique; multiple hyperedges incident upon k vertices; and arbitrary hypergraph in which the edges can contain any set of k vertices. For each of these classes, an algorithm is proposed for constructing the hypergraph from an arbitrary vector. If the construction is impossible, the algorithm determines how much the vector should be reduced so that the hypergraph could be constructed.
ISSN:1064-2307
1555-6530
DOI:10.1134/S1064230714040091