1,721,162 research outputs found
On scheduling series-parallel dags to maximize area
No full textThe AREA of a schedule for executing DAGs is the average number of DAG-chores that are eligible for execution at each step of the computation. AREA maximization is a new optimization goal for schedules that execute DAGs within computational environments, such as Internet-based computing, clouds, and volunteer computing projects, that are dynamically heterogeneous, in the sense that the environments' constituent computers can change their effective powers at times and in ways that are not predictable. This paper is motivated by the thesis that, within dynamically heterogeneous environments, DAG-schedules that have larger AREAs execute a computation-DAG with smaller completion time under many circumstances; this thesis is supported by preliminary simulation-based experiments. While every DAG admits an AREA-maximizing schedule, it is likely computationally difficult to find such a schedule for an arbitrary DAG. Earlier work has shown how to craft AREA-maximizing schedules efficiently for a number of families of DAGs whose structures are reminiscent of many scientific computations. The current paper extends this work by showing how to efficiently craft AREA-maximizing schedules for series-parallel DAGs, a family that models a multithreading computing paradigm. The techniques for crafting these schedules promise to apply also to other large families of recursively defined DAGs. Moreover, the ability to derive these schedules efficiently leads to an efficient AREA-oriented heuristic for scheduling arbitrary DAGs. © World Scientific Publishing Company
Emotional valence and gender effects on willingness to interact with virtual agents in people with depressive symptoms
No full textDual 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
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
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
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
The online abstraction problem for Euler diagrams
No full textA Euler diagrams are an accessible and effective visualisation of data involving simple set-theoretic relationships. Efficient algorithms to quickly compute the abstract regions of an Euler diagram upon curve addition and removal have been developed, but a strict set of drawing conventions (called wellformed-ness conditions) were enforced, meaning that some abstract diagrams are not representable as concrete diagrams. We present a variation and extension of the methodology which enables region computations for Euler diagrams under the relaxation of several drawing conventions. We provide complexity analysis and compare with the previous methodology. The algorithms are presented for generic curves, allowing for specialisations such as utilising fixed geometric shapes for curves that often occur in applications
- …
