作者:
Tamura, YumaIto, TakehiroZhou, XiaoTohoku Univ
Grad Sch Informat Sci Sendai Miyagi 9808579 Japan JST
ERATO Kawarabayashi Large Graph Project Global Res Ctr Big Data MathNII Tokyo 1018430 Japan
A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the proble...
详细信息
A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.
We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a lis...
详细信息
We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives sharp analyses of the problem with respect to pathwidth.
graph structure which is often used to model the relationship between the data items has drawn more and more attention. The graph datasets from many important domains have the property called scale-free. In the scale-...
详细信息
ISBN:
(纸本)9781479980062
graph structure which is often used to model the relationship between the data items has drawn more and more attention. The graph datasets from many important domains have the property called scale-free. In the scale-free graphs, there exist the hubs, which have much larger degree than the average value. The hubs may cause the problems of load imbalance, poor scalability and high communication overhead when the graphs are processed in the distributed memory systems. In this paper, we design an asynchronous graph processing framework targeted for distributed memory by considering the hubs as a separate part of the vertexes, which we call it the hub-centric idea. Specifically speaking, a hub-duplicate graph partitioning method is proposed to balance the workload and reduce the communication overhead. At the same time, an efficient asynchronous state synchronization method for the duplicates is also proposed. In addition, a priority scheduling strategy is applied to further reduce the communication overhead.
The problem of finding the minimum cut of an undirected unweighted graph is studied on the external memory model. First, a lower bound of Omega((E/V)Sort(V)) on the number of I/Os is shown for the problem, where V is ...
详细信息
The problem of finding the minimum cut of an undirected unweighted graph is studied on the external memory model. First, a lower bound of Omega((E/V)Sort(V)) on the number of I/Os is shown for the problem, where V is the number of vertices and E is the number of edges. Then the following are presented, (1) a deterministic minimum cut algorithm that uses O(min{c(7) (log(3+is an element of) E)(MST(V, E)), c(log E)(MST(V, E)) + (V /root M) Sort(V)}) I/Os;here is an element of > 0 is a small constant, MST(V, E) is the number of I/Os needed to compute a minimum spanning tree of the graph, and c is the value of the minimum cut. The algorithm performs better on dense graphs than the algorithm of [1], which requires O(E + c(2)V log(V/c)) I/Os, when executed on the external memory model. For a delta-fat graph (for delta > 0, the maximum tree packing of the graph is at least (I + delta)c/2), our algorithm computes a minimum cut in O(c(log E)MST(V, E)) I/Os. (2) A randomized algorithm that computes minimum cut with high probability in O(c(log E).MST(V, E) Sort(E) log(2) V + V/B Sort(V) log V) I/Os. (3) A (2 + is an element of)-minimum cut algorithm that requires O((E/V) MST(V, E)) I/Os. (C) 2014 Elsevier B.V. All rights reserved.
Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar l(b)vertical bar =vertical bar I-r vertical bar and imagine that a token is placed on each vertex in I-b. Then, the SLIDING ...
详细信息
Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar l(b)vertical bar =vertical bar I-r vertical bar and imagine that a token is placed on each vertex in I-b. Then, the SLIDING TOKEN problem is to determine whether there exists a sequence of independent sets which transforms I-b into I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time;(2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I-b and I-r whose length (i.e., the number of token-slides) is quadratic;and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. (C) 2015 Elsevier B.V. All rights reserved.
The property M(k) is a concept associated with the unique list coloring. A graph G has the property M(k) if for any collection of lists assigned to its vertices, each of size k, either there is no list coloring for G ...
详细信息
The property M(k) is a concept associated with the unique list coloring. A graph G has the property M(k) if for any collection of lists assigned to its vertices, each of size k, either there is no list coloring for G or there are at least two k-list colorings. The existing research results indicate that K-1,K-1,K-1,K-r and K-1*r,K-3 have the property M(3), and in addition K-1*5,K-r and K-1*r,K-5 have the property M(4) for every r >= 2. The results above are extended to every k in this paper. We will show that for every r >= 1, k >= 2, K-1*r,K- (2k-3) and K-1*(2k-3),K-r have the property M(k). The conclusion will pave the way to characterizing unique k-list colorable complete multipartite graphs. (C) 2014 Elsevier B.V. All rights reserved.
Let GA be a hereditary family of graphs and Ha hereditary family of acyclically directed family of graphs. A graph G(V, E) is a GA-H reduced graph if it can be obtained from a graph GA(V, D) is an element of GA by del...
详细信息
Let GA be a hereditary family of graphs and Ha hereditary family of acyclically directed family of graphs. A graph G(V, E) is a GA-H reduced graph if it can be obtained from a graph GA(V, D) is an element of GA by deleting the edges of an edge subgraph H(V, E') is an element of H. The GA-H reduced graphs are a generalization of the complements of the H-mixed graphs. Examples of such families of GA-H reduced graphs are the interval filament graphs, the subtree filament graphs, the circular-arc filament graphs, the cactus subtree filament graphs, the 3D-interval-filament graphs and the subgraph overlap graphs. We describe polynomial time algorithms for various problems on GA-H reduced graphs, when the families GA and H have specific properties. The algorithms are to find maximum independent sets, maximum K-packings, maximum cliques, maximum induced complete bipartite subgraphs, maximum weight holes of a given parity and antiholes of a given parity. (C) 2015 Elsevier B.V. All rights reserved.
The breadth-first search (BFS) is one of the most centric kernels in graph processing. Beamer's direction-optimizing BFS algorithm, which selects one of two traversal directions at each level, can reduce unnecessa...
详细信息
ISBN:
(纸本)9781467378130
The breadth-first search (BFS) is one of the most centric kernels in graph processing. Beamer's direction-optimizing BFS algorithm, which selects one of two traversal directions at each level, can reduce unnecessary edge traversals. In a previous paper, we presented an efficient BFS for a non-uniform memory access (NUMA)-based system, in which the NUMA architecture was carefully considered. In this paper, we investigate the locality of memory accesses in terms of the communication with remote memories in a BFS for a NUMA system, and describe a fast and highly scalable implementation. Our new implementation achieves performance rates of 174.704 billion edges per second for a Kronecker graph with 2(33) vertices and 2(37) edges on two racks of a SGI UV 2000 system with 1,280 threads. The implementations described in this paper achieved the fastest entries for a shared-memory system in the June 2014 and November 2014 graph500 lists, and produced the most energy-efficient entries in the second, third, and fourth Green graph500 lists (big data category).
We implement a promising algorithm for sparse-matrix sparse-vector multiplication (SpMSpV) on the GPU. An efficient k-way merge lies at the heart of finding a fast parallel SpMSpV algorithm. We examine the scalability...
详细信息
ISBN:
(纸本)9781467376846
We implement a promising algorithm for sparse-matrix sparse-vector multiplication (SpMSpV) on the GPU. An efficient k-way merge lies at the heart of finding a fast parallel SpMSpV algorithm. We examine the scalability of three approaches-no sorting, merge sorting, and radix sorting-in solving this problem. For breadth-first search (BFS), we achieve a 1.26x speedup over state-of-the-art sparse-matrix dense-vector (SpMV) implementations. The algorithm seems generalizeable for single-source shortest path (SSSP) and sparse-matrix sparse-matrix multiplication, and other core graph primitives such as maximal independent set and bipartite matching.
Depth-First Search (DFS), which traverses a graph in the depth-first order, is one of the fundamental graph operations, and the result of DFS over all nodes in G is a spanning tree known as a D ES-Tree. There are many...
详细信息
ISBN:
(纸本)9781450327589
Depth-First Search (DFS), which traverses a graph in the depth-first order, is one of the fundamental graph operations, and the result of DFS over all nodes in G is a spanning tree known as a D ES-Tree. There are many graph algorithms that need DFS such as connected component computation, topological sort, community detection, eulerian path computation, graph bipartiteness testing, planar graph testing, etc, because the in-memory DFS algorithm shows it can be done in linear time w.r.t. the size of G. However, given the fact that real-world graphs grow rapidly in the big data era, the in-memory DFS algorithm cannot be used to handle a large graph that cannot be entirely held in main memory. In this paper, we focus on I/O efficiency and study semi-external algorithms to DFS a graph G which is on disk. Here, like the existing semi-external algorithms, we assume that a spanning tree of G can be held in main memory and the remaining edges of G are kept on disk, and compute the DFS-Tree in main memory with which DFS can be identified. We propose novel divide & conquer algorithms to DFS over a graph G on disk. In brief, we divide a graph into several subgraphs, compute the DFS-Tree for each subgraph independently, and then merge them together to compute the DES-Tree for the whole graph. With the global DES-Tree computed we identify DFS. We discuss the valid division, that can lead to the correct DFS, and the challenges to do so. We propose two division algorithms, named Divide-Star and Divide-TD, and a merge algorithm. We conduct extensive experimental studies using four real massive datasets and several synthetic datasets to confirm the I/O efficiency of our approach.
暂无评论