1,721,036 research outputs found
Some observations on the physical realizability of compartmental models with delays.
No full textOften a compartmental model must include delays to fit the experimental observations. The resulting dynamical equations are difference-differential equations and must satisfy certain conditions if they represent a physically realizable system. The physical realizability of two compartmental models with delays is discussed
Improved Algorithms and Bounds for List Union-Free Families
No full textList 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
Selected Algorithmic Papers from the International Workshop on Combinatorial Algorithms 2024
No full textThis 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 [...
Low-weight superimposed codes and related combinatorial structures: Bounds and applications
No full textA (k,n)-superimposed code is a well known and widely used combinatorial structure that can be represented by a t×n binary matrix such that for any k columns of the matrix and for any column c chosen among these k columns, there exists a row in correspondence of which column c has an entry equal to 1 and the remaining k−1 columns have entries equal to 0. Due to the many situations in which superimposed codes find applications, there is an abundant literature that studies the problem of constructing (k,n)-superimposed codes with a small number t of rows. Motivated by applications to conflict-free communication in multiple-access networks, group testing, and data security, we study the problem of constructing superimposed codes that have the additional constraints that the number of 1's in each column of the matrix is constant, and equal to an input parameter w. Our results improve on the known literature in the area. We also extend our findings to other important combinatorial structures, like selectors, generalized superimposed codes, and z-error correcting superimposed codes
Dual domination problems in graphs
No full textWe introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in a network are partitioned into two categories: Positive nodes (V+) and negative nodes (V−). We study the Maximum Bounded Dual Domination, where, given a bound k, the problem is to find a set D⊆V+, which maximizes the number of nodes dominated in V+, dominating at most k nodes in V−. We show that such problem is hard to approximate to a factor better than (1−1/e). We give a polynomial time algorithm with approximation guaranteed (1−e−1/Δ), where Δ represents the maximum number of neighbors in V+ of any node in V−, and an O(|V|k2) time algorithm to solve the problem on trees. We also study two related problems named Maximum Dual Domination and minimum Negative Dual Domination. For both problems, we show hardness results and provide O(|V|) time algorithms on trees
Parameterized complexity for iterated type partitions and modular-width
No full textThis paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the EQUITABLE COLORING problem is W[1]-hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of EQUITABLE COLORING when parameterized by modular-width. On the contrary, we show that the EQUITABLE COLORING problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the MAXIMUM CLIQUE, MINIMUM GRAPH COLORING, (TOTAL) MINIMUM DOMINATING SET, MINIMUM VERTEX COVER and MAXIMUM INDEPENDENT SET problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above
Graph Burning in Community-based Networks
No full textGraph 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 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
Immunization in the Threshold Model: A Parameterized Complexity Study
No full textWe consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node’s resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and l, is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most l nodes? We consider several parameters associated with the input, including the bounds k and l, the maximum node degree Δ , the number ζ of initially contaminated nodes, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations
- …
