Search
Abstract
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.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (3)
-
Krzysztof Turowski dr inż.
- Uniwersytet Jagielloński
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 915,
pages 11 - 25,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2022
- Bibliographic description:
- Janczewski R., Obszarski P., Turowski K.: Weighted 2-sections and hypergraph reconstruction// THEORETICAL COMPUTER SCIENCE -Vol. 915, (2022), s.11-25
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2022.02.016
- Verified by:
- Gdańsk University of Technology
seen 130 times