Article number 5
Published in RGT on November 18, 2020

Creation of the mathematical apparatus for establishing the duality relation between the vertex separators and cuts in hypergraphs

Keywords:
strict line hypergraph, vertex separator, cut, line graph, involution, hypergraph

Abstract:

The article introduces the pioneered concept of the strict line hypergraph and proves that the function of its formation is an involution. This background forms the basis for specifying the duality relation between the vertex separators and cuts in hypergraphs. All significant considerations are presented in the form of theorems accompanied with their rigorous proofs and discussions of the specific situations.

References:

1. A. Potebnia, "Representation of the Greedy Algorithms Applicability for Solving the Combinatorial Optimization Problems Based on the Hypergraph Mathematical Structure", The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM) 14th International Conference on, pp. 328-332, 2017.

View in Google Scholar

2. A. Potebnia, "Method for Classification of the Computational Problems on the Basis of the Multifractal Division of the Complexity Classes", Problems of Infocommunications. Science and Technology (PIC S&T) Third International Scientific-Practical Conference on, pp. 1-4, 2016.

View in Google Scholar

3. T. Evans and R. Lambiotte, "Line graphs link partitions and overlapping communities", Phys. Rev. E, vol. 80, no. 1, pp. 016105, 2009.

View in Google Scholar

Full Text:

2020

Abstract viewed:
15

PDF downloaded:
5
How to Cite:
IEEE Citation Style
▾
  • IEEE Citation Style
  • ACM Citation Style
  • APA Citation Style
  • Harvard Citation Style
  • MLA Citation Style
  • Turabian Citation Style
  • Chicago Citation Style
A. Potebnia, “Creation of the mathematical apparatus for establishing the duality relation between the vertex separators and cuts in hypergraphs,” 12th International Scientific and Technical Conference on Computer Science and Information Technologies, pp. 236 – 239, 2017. DOI: 10.​1109/​STC-CSIT.​2017.​​8098777. Open-access version available at https://purl.org/artempotebnia/5
Section:
Original Scientific Articles in Graph Theory
Universal Resource Name:
https:/
/
purl.
org/
artempotebnia/
5
Reading Tools:
Creation of the mathematical apparatus for establishing the duality relation between the vertex separators and cuts in hypergraphs

Authored by: Artem Potebnia
ORCID: https://orcid.org/0000-0002-8162-5613

Keywords: strict line hypergraph, vertex separator, cut, line graph, involution, hypergraph

Abstract: The article introduces the pioneered concept of the strict line hypergraph and proves that the function of its formation is an involution. This background forms the basis for specifying the duality relation between the vertex separators and cuts in hypergraphs. All significant considerations are presented in the form of theorems accompanied with their rigorous proofs and discussions of the specific situations.