Adele Anna Rescigno
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Adele Anna Rescigno has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Luisa Gargano
University of Salerno
16 shared publications - Gennaro Cordasco
University of Salerno
14 shared publications - Ugo Vaccaro
Department of Computer Science, University of Salerno, Fisciano, Italy
9 shared publications - Marco Dalai
Department of Information Engineering University of Brescia Brescia Italy
3 shared publications - Stefano Della Fiore
Univ Salerno, DI, Via Giovanni Paolo II 132, I-84084 Fisciano, Italy
2 shared publications Jean-Claude Bermond
MASCOTTE, joint project CNRS-INRIA-UNSA, 06902 Sophia-Antipolis, France
1 shared publication
Latest Publications
- Open Access
- 30 May 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (6) , 328
Selected Algorithmic Papers from the International Workshop on Combinatorial Algorithms 2024
This Special Issue is dedicated to a selection of papers from the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024), held in July 2024, in Ischia, Italy, with Adele A
- 30 May 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (6) , 328
Open AccessSelected Algorithmic Papers from the International Workshop on Combinatorial Algorithms 2024
This Special Issue is dedicated to a selection of papers from the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024), held in July 2024, in Ischia, Italy, with Adele A
- 21 February 2025
- Published by Springer Nature
- p. 94-110
Parameterized Complexity of (d, r)-Domination via Modular Decomposition
- 21 February 2025
- Published by Springer Nature
- p. 94-110
Parameterized Complexity of (d, r)-Domination via Modular Decomposition
- Open Access
Distance Vector Domination
Identifying and mitigating the spread of fake information is a challenging issue that has become dominant with the rise of social media. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, once immunized, can prevent the spreading of fake narratives. The considered problem, named {\em Distance Vector Domination} generalizes both distance and multiple domination, at individual (i.e., vertex) level. We study the parameterized complexity of the problem according to several standard and structural parameters. We prove the W[1]-hardness of the problem with respect to neighborhood diversity, even when all the distances are $1$. We also give fixed-parameter algorithms for some variants of the problem and parameter combinations.Open AccessDistance Vector Domination
Identifying and mitigating the spread of fake information is a challenging issue that has become dominant with the rise of social media. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, once immunized, can prevent the spreading of fake narratives. The considered problem, named {\em Distance Vector Domination} generalizes both distance and multiple domination, at individual (i.e., vertex) level. We study the parameterized complexity of the problem according to several standard and structural parameters. We prove the W[1]-hardness of the problem with respect to neighborhood diversity, even when all the distances are $1$. We also give fixed-parameter algorithms for some variants of the problem and parameter combinations. - 13 September 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 360, 181-187
An efficient algorithm for group testing with runlength constraints
- 13 September 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 360, 181-187
An efficient algorithm for group testing with runlength constraints
- Open Access
- 10 September 2024
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 28 (3) , 11-30
Graph Burning in Community-based Networks
Graph burning is a deterministic, discrete-time process that can be used to model how influence or contagion spreads in a graph. In the graph burning process, each node starts as dormant, and becomes informed/burned over time; when a node is burned, it remains burned until the end of the process. In each round, one can burn a new node (source of fire) in the network. Once a node is burned in round $t$, in round $t+1$, each of its dormant neighbors becomes burned. The process ends when all nodes are burned; the goal is to minimize the number of rounds.We study a variation of graph burning in order to model spreading processes in community-based networks. With respect to a specific piece of information, a community is {\em satisfied} when this information reaches at least a prescribed number of its members. Specifically, we consider the problem of identifying a minimum length sequence of nodes that, according to a graph burning process, allows to satisfy all the communities of the network. We investigate this NP-hard problem from an approximation point of view, showing both a lower bound and a matching upper bound. We also investigate the case when the number of communities is constant and show how to solve the problem with a constant approximation factor.Moreover, we consider the problem of maximizing the number of satisfied groups, given a budget $k$ on the number of rounds.- 10 September 2024
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 28 (3) , 11-30
Open AccessGraph Burning in Community-based Networks
Graph burning is a deterministic, discrete-time process that can be used to model how influence or contagion spreads in a graph. In the graph burning process, each node starts as dormant, and becomes informed/burned over time; when a node is burned, it remains burned until the end of the process. In each round, one can burn a new node (source of fire) in the network. Once a node is burned in round $t$, in round $t+1$, each of its dormant neighbors becomes burned. The process ends when all nodes are burned; the goal is to minimize the number of rounds.We study a variation of graph burning in order to model spreading processes in community-based networks. With respect to a specific piece of information, a community is {\em satisfied} when this information reaches at least a prescribed number of its members. Specifically, we consider the problem of identifying a minimum length sequence of nodes that, according to a graph burning process, allows to satisfy all the communities of the network. We investigate this NP-hard problem from an approximation point of view, showing both a lower bound and a matching upper bound. We also investigate the case when the number of communities is constant and show how to solve the problem with a constant approximation factor.Moreover, we consider the problem of maximizing the number of satisfied groups, given a budget $k$ on the number of rounds. - Open Access
An Efficient Algorithm for Group Testing with Runlength Constraints
In this paper, we provide an efficient algorithm to construct almost optimal $(k,n,d)$-superimposed codes with runlength constraints. A $(k,n,d)$-superimposed code of length $t$ is a $t \times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. These combinatorial structures were introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. By using Moser and Tardos' constructive version of the Lovász Local Lemma, we provide an efficient randomized Las Vegas algorithm of complexity $Θ(t n^2)$ for the construction of $(k,n,d)$-superimposed codes of length $t=O(dk\log n +k^2\log n)$. We also show that the length of our codes is shorter, for $n$ sufficiently large, than that of the codes whose existence was proved in [1].Open AccessAn Efficient Algorithm for Group Testing with Runlength Constraints
In this paper, we provide an efficient algorithm to construct almost optimal $(k,n,d)$-superimposed codes with runlength constraints. A $(k,n,d)$-superimposed code of length $t$ is a $t \times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. These combinatorial structures were introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. By using Moser and Tardos' constructive version of the Lovász Local Lemma, we provide an efficient randomized Las Vegas algorithm of complexity $Θ(t n^2)$ for the construction of $(k,n,d)$-superimposed codes of length $t=O(dk\log n +k^2\log n)$. We also show that the length of our codes is shorter, for $n$ sufficiently large, than that of the codes whose existence was proved in [1]. Getting linear time in graphs of bounded neighborhood diversity
Parameterized complexity, introduced to efficiently solve NP‐hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity () for several graph theoretic problems in : Maximum ‐Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular‐width () and consequently—as is a special case of —by . However, the proposed novel algorithms allow for improving the computational complexity from time —where and denote, respectively, the number of vertices and edges in the input graph—to time which is only additive in the size of the input. Then we consider some classical NP‐hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.
Getting linear time in graphs of bounded neighborhood diversity
Parameterized complexity, introduced to efficiently solve NP‐hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity () for several graph theoretic problems in : Maximum ‐Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular‐width () and consequently—as is a special case of —by . However, the proposed novel algorithms allow for improving the computational complexity from time —where and denote, respectively, the number of vertices and edges in the input graph—to time which is only additive in the size of the input. Then we consider some classical NP‐hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.
- 20 March 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 350, 100-122
Parameterized complexity for iterated type partitions and modular-width
- 20 March 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 350, 100-122
Parameterized complexity for iterated type partitions and modular-width
- 18 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (4) , 2456-2463
Improved Algorithms and Bounds for List Union-Free Families
List union-free families are basic combinatorial structures that appear in different application scenarios, most notably in one-bit compressed sensing. In this paper, we study algorithms for the construction of list union-free families and we provide bounds on the parameters of these families that substantially affect the complexity of the algorithms that utilize them.
- 18 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (4) , 2456-2463
Improved Algorithms and Bounds for List Union-Free Families
List union-free families are basic combinatorial structures that appear in different application scenarios, most notably in one-bit compressed sensing. In this paper, we study algorithms for the construction of list union-free families and we provide bounds on the parameters of these families that substantially affect the complexity of the algorithms that utilize them.