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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

An important problem in network science is finding an optimal placement ofsensors in nodes in order to uniquely detect failures in the network. Thisproblem can be modelled as an identifying code set (ICS) problem, introduced byKarpovsky et al. in 1998. The ICS problem aims to find a cover of a set $S$,s.t. the elements in the cover define a unique signature for each of theelements of $S$, and to minimise the cover's cardinality. In this work, westudy a generalised identifying code set (GICS) problem, where a uniquesignature must be found for each subset of $S$ that has a cardinality of atmost $k$ (instead of just each element of $S$). The concept of an independentsupport of a Boolean formula was introduced by Chakraborty et al. in 2014 tospeed up propositional model counting, by identifying a subset of variableswhose truth assignments uniquely define those of the other variables.  In this work, we introduce an extended version of independent support,grouped independent support (GIS), and show how to reduce the GICS problem tothe GIS problem. We then propose a new solving method for finding a GICS, basedon finding a GIS. We show that the prior state-of-the-art approaches yieldinteger-linear programming (ILP) models whose sizes grow exponentially with theproblem size and $k$, while our GIS encoding only grows polynomially with theproblem size and $k$. While the ILP approach can solve the GICS problem onnetworks of at most 494 nodes, the GIS-based method can handle networks of upto 21363 nodes; a $\sim 40\times$ improvement. The GIS-based method shows up toa $520\times$ improvement on the ILP-based method in terms of median solvingtime. For the majority of the instances that can be encoded and solved by bothmethods, the cardinality of the solution returned by the GIS-based method isless than $10\%$ larger than the cardinality of the solution found by the ILPmethod.

Solving the Identifying Code Set Problem with Grouped Independent Support