English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

For an even integer t \geq 2, the Matchings Connecivity matrix H_t is amatrix that has rows and columns both labeled by all perfect matchings of thecomplete graph K_t on t vertices; an entry H_t[M_1,M_2] is 1 if M_1\cup M_2 isa Hamiltonian cycle and 0 otherwise. Motivated by the computational study ofthe Hamiltonicity problem, we present three results on the structure of H_t: Wefirst show that H_t has rank at most 2^{t/2-1} over GF(2) via an appropriatefactorization that explicitly provides families of matchings X_t forming basesfor H_t. Second, we show how to quickly change representation between suchbases. Third, we notice that the sets of matchings X_t induce permutationmatrices within H_t.  Subsequently, we use the factorization to obtain an 1.888^n n^{O(1)} timeMonte Carlo algorithm that solves the Hamiltonicity problem in directedbipartite graphs. Our algorithm as well counts the number of Hamiltonian cyclesmodulo two in directed bipartite or undirected graphs in the same time bound.Moreover, we use the fast basis change algorithm from the second result topresent a Monte Carlo algorithm that given an undirected graph on n verticesalong with a path decomposition of width at most pw decides Hamiltonicity in(2+\sqrt{2})^{pw}n^{O(1)} time. Finally, we use the third result to show thatfor every \epsilon >0 this cannot be improved to(2+\sqrt{2}-\epsilon)^{pw}n^{O(1)} time unless the Strong Exponential TimeHypothesis fails, i.e., a faster algorithm for this problem would imply thebreakthrough result of a (2-\epsilon)^n time algorithm for CNF-Sat.

Fast Hamiltonicity checking via bases of perfect matchings