There are many methods to estimate the quasistationary infected fraction of the SIS process on (random) graphs. A challenge is to adequately incorporate correlations, which is especially important in sparse graphs. Me...
详细信息
There are many methods to estimate the quasistationary infected fraction of the SIS process on (random) graphs. A challenge is to adequately incorporate correlations, which is especially important in sparse graphs. Methods typically are either significantly biased in sparse graphs, or computationally very demanding already for small network sizes. The former applies to heterogeneous mean field and to the N-intertwined mean field approximation, the latter to most higher order approximations. In this paper we introduce a method to determine the infected fraction in sparse graphs, which we test on Erdős-Rényi graphs. Our method is based on degree pairs, does take into account correlations, and gives accurate estimates. At the same time, computations are very feasible and can easily be done even for large networks.
Finding the connected components of an undirected graph is one of the most fundamental graph problems. Connected components are used in a wide spectrum of applications including VLSI design, machine learning and image...
详细信息
ISBN:
(纸本)9781665481069
Finding the connected components of an undirected graph is one of the most fundamental graph problems. Connected components are used in a wide spectrum of applications including VLSI design, machine learning and image analysis. Sequentially, one can easily find all connected components in linear time using breadth-first traversal. However, in a massively distributed setting, finding connected components in a scalable way becomes much harder due to data irregularities and the overhead associated with the increased need for communication. In this work, we present a communication-efficient distributed graph algorithm for finding connected components that scales to massively parallel machines. Our algorithm is based on a recent linear-work shared-memory parallel algorithm by Blelloch et al. [1] and refines it for a distributed memory setting. This includes a communication-efficient graph contraction procedure, as well as a distributed variant of the low diameter decomposition by Miller et al. [2]. We tackle the data irregularities introduced by high degree vertices by using an efficient procedure for distributing their incident edges. Our experimental evaluation on up to 16 384 cores indicates a good weak scaling behavior that outperforms current state-of-the-art algorithms.
Aggregate Programming (AP) is a paradigm for developing applications that execute on a fully distributed network of communicating, resource-constrained, spatially-situated nodes (e.g., drones, wireless sensors, etc.)....
详细信息
ISBN:
(纸本)9783031197581;9783031197598
Aggregate Programming (AP) is a paradigm for developing applications that execute on a fully distributed network of communicating, resource-constrained, spatially-situated nodes (e.g., drones, wireless sensors, etc.). In this paper, we address running an AP application on a high-performance, centralized computer such as the ones available in a cloud environment. As a proof of concept, we present preliminary results on the computation of graph statistics for centralised data sets, by extending FCPP, a C++ library implementing AP. This: (i) opens the way to the application of the AP paradigm to problems on large centralised graph-based data structures, enabling massive parallelisation across multiple machines, dynamically joining and leaving the computation;and (ii) represents a first step towards developing collective adaptive systems where computations dynamically move across the IoT/edge/fog/cloud continuum, based on mutable conditions such as availability of resources and network infrastructures.
We refine the weighted type graph technique for proving termination of double pushout (DPO) graph transformation systems. We increase the power of the approach for graphs, we generalize the technique to other categori...
详细信息
We present Atos, a task-parallel GPU dynamic scheduling framework that is especially targeted at dynamic irregular applications. Compared to the dominant Bulk Synchronous Parallel (BSP) frameworks, Atos exposes additi...
详细信息
ISBN:
(纸本)9781450397339
We present Atos, a task-parallel GPU dynamic scheduling framework that is especially targeted at dynamic irregular applications. Compared to the dominant Bulk Synchronous Parallel (BSP) frameworks, Atos exposes additional concurrency by supporting task-parallel formulations of applications with relaxed dependencies, achieving higher GPU utilization, which is particularly significant for problems with concurrency bottlenecks. Atos also offers implicit task-parallel load balancing in addition to data-parallel load balancing, providing users the flexibility to balance between them to achieve optimal performance. Finally, Atos allows users to adapt to different use cases by controlling the kernel strategy and task-parallel granularity. We demonstrate that each of these controls is important in practice. We evaluate and analyze the performance of Atos vs. BSP on three applications: breadth-first search, PageRank, and graph coloring. Atos implementations achieve geomean speedups of 3.44x, 2.1x, and 2.77x and peak speedups of 12.8x, 3.2x, and 9.08x across three case studies, compared to a state-of-the-art BSP GPU implementation. Beyond simply quantifying the speedup, we extensively analyze the reasons behind each speedup. This deeper understanding allows us to derive general guidelines for how to select the optimal Atos configuration for different applications. Finally, our analysis provides insights for future dynamic scheduling framework designs.
We study the decentralized online regularized linear regression algorithm over random time-varying graphs. At each time step, every node runs an online estimation algorithm consisting of an innovation term processing ...
详细信息
The graph searches Breadth First Search (BFS) and Depth First Search (DFS) and the spanning trees constructed by them are some of the most basic concepts in algorithmic graph theory. BFS trees are first -in trees, i.e...
详细信息
The graph searches Breadth First Search (BFS) and Depth First Search (DFS) and the spanning trees constructed by them are some of the most basic concepts in algorithmic graph theory. BFS trees are first -in trees, i.e., every vertex is connected to its first visited neighbor. DFS trees are last -in trees, i.e., every vertex is connected to the last visited neighbor before it. The problem whether a given spanning tree can be the first -in tree or last -in tree of a graph search ordering was introduced in the 1980s and has been studied for several graph searches and graph classes. Here, we consider the problem of deciding whether a given spanning tree of a bipartite graph can be a first -in tree or a last -in tree of the Lexicographic Breadth First Search (LBFS), a special variant of BFS that is commonly used in graph algorithms. We show that the recognition of both first -in trees and last -in trees of LBFS is NP -hard even if the start vertex of the search ordering is fixed and the height of the tree is four. We prove that the bound on the height is tight (unless P = NP) by showing that for all spanning trees of bipartite graphs with height smaller than four we can solve both search tree recognition problems of LBFS in polynomial time. Finally, we give a linear -time algorithm that solves both problems for chordal bipartite graphs and fixed start vertices.
In this work, we study the parameter hull number in a recently defined graph convexity called Cycle Convexity, whose definition is motivated by related notions in Knot Theory. For a graph G = (V, E), define the interv...
详细信息
In this work, we study the parameter hull number in a recently defined graph convexity called Cycle Convexity, whose definition is motivated by related notions in Knot Theory. For a graph G = (V, E), define the interval function in the Cycle Convexity as Icc(S) = S ? {v & ISIN;V (G) | there is a cycle C in G such that V(C) \ S = {v}}, for every S & SUBE;V (G). We say that S & SUBE;V (G) is convex if Icc(S) = S. The convex hull of S & SUBE;V (G), denoted by Hull(S), is the inclusion-wise minimal convex set S' such that S & SUBE;S'. A set S & SUBE;V (G) is called a hull set if Hull(S) = V (G). The hull number of G in the cycle convexity, denoted by hncc(G), is the cardinality of a smallest hull set of G. We first focus on the class of planar graphs, as the main motivation for the definition of hncc(G) stems from Knot Theory and occurs when G is a 4-regular planar graph. We prove that: the hull number of a 4-regular planar graph is at most half of its number of vertices and that such bound is tight;and that deciding whether hncc(G) & LE;k, provided a positive integer k and a planar graph G, is an NP-complete problem. On the positive side, we present polynomial-time algorithms to compute the hull number in the cycle convexity of chordal graphs, P4-sparse graphs, and grids.& COPY;2023 Elsevier B.V. All rights reserved.
Given a bipartite graph G, the Bicluster Editing problem asks for the minimum number of edges to insert or delete in G so that every connected component is a bicluster, i.e. a complete bipartite graph. This has severa...
详细信息
Given a bipartite graph G, the Bicluster Editing problem asks for the minimum number of edges to insert or delete in G so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter k, which is the number of allowed modified edges. We first show that one can obtain a kernel with 4.5k vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time O & lowast;(2.581k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(2.581<^>k)$$\end{document}. Our algorithm has the advantage of being conceptually simple and should be easy to implement.
For a graph G = (V, E), a subset D of vertex set V, is a dominating set of G if every vertex not in D is adjacent to atleast one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paire...
详细信息
ISBN:
(纸本)9783030950170;9783030950187
For a graph G = (V, E), a subset D of vertex set V, is a dominating set of G if every vertex not in D is adjacent to atleast one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set), if G[D], the subgraph induced by D in G has a perfect matching. The Min-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the Min-PD problem remains NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the positive side, the problem is efficiently solvable for many graph classes including intervals graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graph. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (in Theor. Comput. Sci., 591(2015) : 99 - 105 and Algorithmica, 82(2020) : 2809 - 2840).
暂无评论