In the paper we introduce the notion of weighted 2-sections of hypergraphs with integer weights and study the following hypergraph reconstruction problems: (1) Given a weighted graph , is there a hypergraph H such that is its weighted 2-section? (2) Given a weighted 2-section , find a hypergraph H such that is its weighted 2-section. We show that (1) is NP-hard even if G is a complete graph or integer weights w does not exceed 2. Next, we show that (2) is solvable in linear time if G is a partial 2-tree, 2-degenerated or its degree does not exceed 4.
Authors
- dr hab. inż. Robert Janczewski link open in new tab ,
- dr Paweł Obszarski link open in new tab ,
- dr inż. Krzysztof Turowski
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.tcs.2022.02.016
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach
- Language
- angielski
- Publication year
- 2022
Source: MOSTWiedzy.pl - publication "Weighted 2-sections and hypergraph reconstruction" link open in new tab
