EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Recursively Constructed Uniform Hypergraphs

Frank Gurski, Jochen Rethmann, Egon Wanke

Algorithms · 14.07.2026 · 19 (7) · 575

DOI: 10.3390/a19070575 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithms, online erschienen am 14.07.2026. Verfasst von Frank Gurski und 2 weiteren Autor:innen. Die Arbeit nennt 63 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this work, we introduce and study a generalization for r-uniform hypergraphs of complement-reducible graphs, the so-called co-graphs. The operations for r-join-hypergraphs are the binary disjoint union of two given r-join-hypergraphs and the r-nary join, which inserts all possible hyperedges of cardinality r, each including exactly one vertex from each of r given r-join-hypergraphs. We characterize the primal graphs of r-join-hypergraphs as special co-graphs and give some properties of r-join-hypergraphs. This allows us to give a method that decides whether an r-uniform input hypergraph H is an r-join-hypergraph and, in the case of an affirmative answer, finds a decomposition tree for H in polynomial time. This task proved to be challenging. We show specific formulas for computing various hypergraph parameters for r-uniform hypergraphs defined by the binary disjoint union of two r-uniform hypergraphs and the r-nary join of r r-uniform hypergraphs. The parameters considered are the size of a largest stable set, the size of a largest co-stable set, the size of a largest independent set, the size of a largest co-independent set, the size of a smallest vertex cover, the size of a smallest 2-transversal, the size of a largest matching, the size of a smallest dominating set, the chromatic number, the strong chromatic number, and the upper chromatic number. This yields O(n·r)-time algorithms to compute these values on r-join-hypergraphs on n vertices given by a decomposition tree. Of particular interest is the development of an efficient algorithm to compute the size of a largest matching. In addition, we infer relations among the considered parameters restricted to r-join-hypergraphs. Our methods generalize and reprove a number of results that are known for co-graphs.

Zitieren

APA

Gurski, F., Rethmann, J., & Wanke, E. (2026). Recursively Constructed Uniform Hypergraphs. Algorithms, 19(7), 575. https://doi.org/10.3390/a19070575

Vancouver

Gurski F, Rethmann J, Wanke E. Recursively Constructed Uniform Hypergraphs. Algorithms. 2026;19(7):575. doi:10.3390/a19070575

BibTeX
@article{Gurski2026,
  author = {Gurski, Frank and Rethmann, Jochen and Wanke, Egon},
  title = {Recursively Constructed Uniform Hypergraphs},
  journal = {Algorithms},
  year = {2026},
  volume = {19},
  number = {7},
  pages = {575},
  doi = {10.3390/a19070575}
}
Kostenlos starten →