We consider conflict-free colorings of graph neighborhoods: Each vertex of the graph must be assigned a color so that for each vertex v there is at least one color appearing exactly once in the ...neighborhood of v. The goal is to minimize the number of used colors. We consider both the case of closed neighborhoods, when the neighborhood of a node includes the node itself, and the case of open neighborhoods when a node does not belong to its neighborhood. In this paper, we study complexity aspects of the problem. We show that the problem of conflict-free coloring of closed neighborhoods is NP-complete. Moreover, we give non-approximability results for the conflict-free coloring of open neighborhoods. From a positive point of view, both problems become tractable if parameterized by the vertex cover number or the neighborhood diversity number of the graph. We present simple algorithms which improve on existing results.
This paper reports on a rare case of pregnancy after uterine artery embolization (UAE) for uterine arteriovenous malformation (AVM). Debate exists about persistence of fertility in women after UAE. ...Adverse effects of this technique can modify both uterine echostructure, inducing necrosis and infarction, endometrial atrophy and uterine artery rupture, and ovarian reserve, causing persistent amenorrhea. Ovarian reserve appears to be affected by UAE in pre-menopausal women. However, younger ovaries (according to biological ovarian age) exhibit a greater capacity for recovery after ovarian damage. Therefore, larger studies are needed for more conclusive results.
A 28-year-old woman was admitted to our department due to life-threatening uterine bleeding, resulting in tachycardia, pallor, and sweating. The patient came with a history of two spontaneous miscarriages. After sonography and computed tomography, AVMs were identified at uterine fundus and anterior wall.
The pathogenesis of infertility after UAE is not yet known. The peculiarity of this case was that, only few months later, the patient became pregnant and gave birth to a live fetus at 37 weeks with cesarean delivery.
This study is the first molecular and biochemical analysis conducted on Pompia, a plant of unknown origin that is endemic to Sardinia; this plant is thought to belong to the Citrus genus. Here, genes ...coding for the enzymes superoxide dismutase (SOD, EC 1.15.1.1), catalase (CAT, EC 1.11.1.6), peroxidase (POD, EC 1.11.1.7), and polyphenol oxidase (PPO, EC 1.14.18.1) were identified. We detected the aforementioned enzymes in fresh leaf tissue and assessed the catalytic activity of each to support the molecular and biochemical data. This was the first molecular study to define the primary structure of proteins with antioxidant activity in Pompia. The study also contributed to the enrichment of gene databases and created the basis for molecular phylogenetic studies, which is important because this plant currently has no taxonomic or phylogenetic classification.
Given a network represented by a graph
G
=
(
V
,
E
)
, we consider a dynamical process of influence diffusion in
G
that evolves as follows: Initially only the nodes of a given
S
⊆
V
are influenced; ...subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The question is to determine a small subset of nodes
S
(
a target set
) that can influence the whole network. This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known that the above optimization problem is hard to approximate within a factor of
2
log
1
-
ϵ
|
V
|
, for any
ϵ
>
0
. In this paper, we present a fast and surprisingly simple algorithm that exhibits the following features: (1) when applied to trees, cycles, or complete graphs, it always produces an optimal solution (i.e, a minimum size target set); (2) when applied to arbitrary networks, it always produces a solution of cardinality which improves on previously known upper bounds; (3) when applied to real-life networks, it always produces solutions that substantially outperform the ones obtained by previously published algorithms (for which no proof of optimality or performance guarantee is known in any class of graphs).
Fault-tolerance and security are desirable properties in communication protocols. In this paper we investigate the use of vertex disjoint spanning trees to obtain efficient, reliable, and secure ...information distribution protocols in the star network. In the first part of the paper we give an efficient algorithm to construct the optimal number of vertex-disjoint spanning trees of the star networks. Subsequently, we present several communication protocols, based on vertex-disjoint spanning trees, exhibiting various degrees of fault-tolerance and security.
We consider the problem of selecting a minimum size subset of nodes in a network that allows to activate all the nodes of the network. We present a fast and simple algorithm that, in real-life ...networks, produces solutions that outperform the ones obtained by using the best algorithms in the literature. We also investigate the theoretical performances of our algorithm and give proofs of optimality for some classes of graphs. From an experimental perspective, experiments also show that the performance of the algorithms correlates with the modularity of the analyzed network. Moreover, the more the influence among communities is hard to propagate, the less the performances of the algorithms differ. On the other hand, when the network allows some propagation of influence between different communities, the gap between the solutions returned by the proposed algorithm and by the previous algorithms in the literature increases.
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.
A wireless network consists of a large number of devices, deployed over a geographical area, and of a base station where data sensed by the devices are collected and accessed by the end users. In ...this paper we study algorithmic and complexity issues originating from the problem of data gathering in wireless networks. We give an algorithm to construct minimum makespan transmission schedules for data gathering under the following hypotheses: the communication graph G is a tree network, the transmissions in the network can interfere with each other up to distance m, where m≥2, and no buffering is allowed at intermediate nodes. In the interesting case in which all nodes in the network have to deliver an arbitrary non-zero number of packets, we provide a closed formula for the makespan of the optimal gathering schedule. Additionally, we consider the problem of determining the computational complexity of data gathering in general graphs and show that the problem is NP-complete. On the positive side, we design a simple (1+2/m)-factor approximation algorithm for general networks.
We introduce a class of generalized superimposed codes that include several cases already studied in the literature. We give bounds on their size and algorithms for their construction.
•We introduce ...a generalization of superimposed codes that includes combinatorial structures already studied in the literature.•We give algorithms for their constructions.•We give bounds on their lengths (the relevant parameter in the application scenarios where superimposed codes are used).•We show that our results improve, on several respects, previously known results.
PDF
