E-viri
Odprti dostop
-
Kim, Hyobeen; Jae-baek, Lee; Siggers, Mark
arXiv (Cornell University), 08/2023Paper, Journal Article
In the problem \({\rm Mix}(H)\) one is given a graph \(G\) and must decide if the Hom-graph \({\rm {\bf Hom}}(G,H)\) is connected. We show that if \(H\) is a triangle-free reflexive graph with at least one cycle, \({\rm Mix}(H)\) is \({\rm coNP}\)-complete. The main part of this is a reduction to the problem \({\rm NonFlat}({\rm{\bf H}})\) for a simplicial complex \({\rm{\bf H}}\), in which one is given a simplicial complex \({\rm{\bf G}}\) and must decide if there are any simplicial maps \(\phi\) from \({\rm{\bf G}}\) to \({\rm{\bf H}}\) under which some \(1\)-cycles of \({\rm{\bf G}}\) maps to homologically non-trivial cycle of \({\rm{\bf H}}\). We show that for any reflexive graph \(H\), if the clique complex \({\rm{\bf H}}\) of \(H\) has a free, non-trivial homology group \(H_1({\rm{\bf H}})\), then \({\rm NonFlat}({\rm{\bf H}})\) is \({\rm NP}\)-complete.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.