The polynomial algorithm for optimal spanning hyperforest problem

2007/02/26 by А. Ш. Абакаров, Abakarov, Alik, Yuri Sushkov +1
Computer Science · Engineering · #05C65 #Advanced Optical Network Technologies #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Software-Defined Networks and 5G

paper · pdf · doi:10.48550/arxiv.math/0702757

openalex publication_date 2007/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper is devoted to one theory of hypergraph connectivity and presents the proof of the polynomial algorithm for finding an optimal spanning hyperforest(hypertree) for any given weighed q-uniform hypergraph.

Related

• A randomized polynomial-time algorithm for the Spanning Hypertree Problem on 3-uniform hypergraphs
• Hypergraph partitions
• Hypergraph Connectivity Augmentation in Strongly Polynomial Time
• Dirac-type conditions for spanning bounded-degree hypertrees
• Identifying the Minimal Transversals of a Hypergraph and Related Problems