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

The problem of enumerating all connected induced subgraphs of a given order$k$ from a given graph arises in many practical applications: bioinformatics,information retrieval, processor design,to name a few. The upper bound on thenumber of connected induced subgraphs of order $k$ is$n\cdot\frac{(e\Delta)^{k}}{(\Delta-1)k}$, where $\Delta$ is the maximum degreein the input graph $G$ and $n$ is the number of vertices in $G$. In this shortcommunication, we first introduce a new neighborhood operator that is the keyto design reverse search algorithms for enumerating all connected inducedsubgraphs of order $k$. Based on the proposed neighborhood operator, threealgorithms with delay of $O(k\cdotmin\{(n-k),k\Delta\}\cdot(k\log{\Delta}+\log{n}))$, $O(k\cdotmin\{(n-k),k\Delta\}\cdot n)$ and $O(k^2\cdot min\{(n-k),k\Delta\}\cdotmin\{k,\Delta\})$ respectively are proposed. The first two algorithms requireexponential space to improve upon the current best delay bound$O(k^2\Delta)$\cite{4} for this problem in the case$k>\frac{n\log{\Delta}-\log{n}-\Delta+\sqrt{n\log{n}\log{\Delta}}}{\log{\Delta}}$and $k>\frac{n^2}{n+\Delta}$ respectively.

Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality