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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It is well known that many local graph problems, like Vertex Cover andDominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E)with a given tree decomposition of width tw. However, for nonlocal problems,like the fundamental class of connectivity problems, for a long time we did notknow how to do this faster than tw^{O(tw)}|V|^{O(1)}. Recently, Cygan et al.(FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivityproblems running in time $c^{tw}|V|^{O(1)} for a small constant c, e.g., forHamiltonian Cycle and Steiner tree. Naturally, this raises the question whetherrandomization is necessary to achieve this runtime; furthermore, it isdesirable to also solve counting and weighted versions (the latter withoutincurring a pseudo-polynomial cost in terms of the weights).  We present two new approaches rooted in linear algebra, based on matrix rankand determinants, which provide deterministic c^{tw}|V|^{O(1)} time algorithms,also for weighted and counting versions. For example, in this time we can solvethe traveling salesman problem or count the number of Hamiltonian cycles. Therank-based ideas provide a rather general approach for speeding up evenstraightforward dynamic programming formulations by identifying "small" sets ofrepresentative partial solutions; we focus on the case of expressingconnectivity via sets of partitions, but the essential ideas should havefurther applications. The determinant-based approach uses the matrix treetheorem for deriving closed formulas for counting versions of connectivityproblems; we show how to evaluate those formulas via dynamic programming.

Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time