1,721,114 research outputs found
A Note on Approximation of Uniform Distributions from Variable-to-Fixed Length Codes
No full textCicalese F, Gargano L, Vaccaro U. A Note on Approximation of Uniform Distributions from Variable-to-Fixed Length Codes. IEEE Transactions on Information Theory. 2006;52(8):3772-3777
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
Contemplazione e mistica in san Pier Damiani
No full textDopo una panoramica sugli studio dedicati alla spiritualità di Pier Damiani si ricercano i temi ascetici e penitenziali nella sua opera e nella sua biografia, con particolare attenzione alle metafore e allo stile. Si passa poi ai temi e al linguaggio mistico, che sublimano la durezza dell'ascesi nella gioia dell'incontro con Dio
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
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
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
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
Getting linear time in graphs of bounded neighborhood diversity
No full textParameterized 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 ((Formula presented.)) for several graph theoretic problems in (Formula presented.) : Maximum (Formula presented.) -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 ((Formula presented.)) and consequently—as (Formula presented.) is a special case of (Formula presented.) —by (Formula presented.). However, the proposed novel algorithms allow for improving the computational complexity from time (Formula presented.) —where (Formula presented.) and (Formula presented.) denote, respectively, the number of vertices and edges in the input graph—to time (Formula presented.) 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
- …
