Weighted 2-sections and hypergraph reconstruction - Publikacja - MOST Wiedzy

Wyszukiwarka

Weighted 2-sections and hypergraph reconstruction

Abstrakt

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.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuły w czasopismach
Opublikowano w:
THEORETICAL COMPUTER SCIENCE nr 915, strony 11 - 25,
ISSN: 0304-3975
Język:
angielski
Rok wydania:
2022
Opis bibliograficzny:
Janczewski R., Obszarski P., Turowski K.: Weighted 2-sections and hypergraph reconstruction// THEORETICAL COMPUTER SCIENCE -Vol. 915, (2022), s.11-25
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2022.02.016
Weryfikacja:
Politechnika Gdańska

wyświetlono 85 razy

Publikacje, które mogą cię zainteresować

Meta Tagi