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

An NP-hard graph problem may be intractable for general graphs but it couldbe efficiently solvable using dynamic programming for graphs with bounded width(or depth or some other structural parameter). Dynamic programming is awell-known approach used for finding exact solutions for NP-hard graph problemsbased on tree decompositions. It has been shown that there exist algorithmsusing linear time in the number of vertices and single exponential time in thewidth (depth or other parameters) of a given tree decomposition for manyconnectivity problems. Employing dynamic programming on a tree decompositionusually uses exponential space. In 2010, Lokshtanov and Nederlof introduced anelegant framework to avoid exponential space by algebraization. Later, F\"urerand Yu modified the framework in a way that even works when the underlying setis dynamic, thus applying it to tree decompositions. In this work, we designspace-efficient algorithms to solve the Hamiltonian Cycle and the TravelingSalesman problems, using polynomial space while the time complexity is onlyslightly increased. This might be inevitable since we are reducing the spaceusage from an exponential amount (in dynamic programming solution) topolynomial. We give an algorithm to solve Hamiltonian cycle in time$\mathcal{O}((4w)^d\, nM(n\log{n}))$ using $\mathcal{O}(dn\log{n})$ space,where $M(r)$ is the time complexity to multiply two integers, each of whichbeing represented by at most $r$ bits. Then, we solve the more generalTraveling Salesman problem in time $\mathcal{O}((4w)^d poly(n))$ using space$\mathcal{O}(\mathcal{W}dn\log{n})$, where $w$ and $d$ are the width and thedepth of the given tree decomposition and $\mathcal{W}$ is the sum of weights.Furthermore, this algorithm counts the number of Hamiltonian Cycles.

A Space-efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraziation