检索结果-内蒙古大学图书馆

algorithms for the Independent Feedback Vertex Set Problem

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1179-1188页

作者： Tamura, Yuma Ito, Takehiro Zhou, Xiao Tohoku 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 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.

关键词： fixed parameter tractability graph algorithm independent feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

The List Coloring Reconfiguration Problem for Bounded Pathwidth graphs

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1168-1178页

作者： Hatanaka, Tatsuhiko Ito, Takehiro Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

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 algorithm list coloring pathwidth PSPACE-complete reachability on solution space reconfiguration

来源：评论

学校读者我要写书评

暂无评论

HAGP: A Hub-centric Asynchronous graph Processing Framework for Scale-free graph 15

HAGP: A Hub-centric Asynchronous Graph Processing Framework ...

引用

2015 15th IEEE ACM International Symposium on Cluster Cloud and Grid Computing (CCGrid 2015)

作者： Gao, Tao Lu, Yutong Zhang, Baida Natl Univ Def Technol Coll Comp Changsha Hunan Peoples R China

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.

关键词： graph processing graph algorithm parallel algorithm distributed computing

来源：评论

学校读者我要写书评

暂无评论

I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年第1期575卷 33-41页

作者： Bhushan, Alka Sajith, G. Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 Assam India

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.

关键词： graph algorithm External memory algorithm I/O complexity Minimum cut Lower bound

来源：评论

学校读者我要写书评

暂无评论

Linear-time algorithm for sliding tokens on trees

引用

THEORETICAL COMPUTER SCIENCE 2015年 600卷 132-142页

作者： Demaine, Erik D. Demaine, Martin L. Fox-Epstein, Eli Hoang, Duc A. Ito, Takehiro Ono, Hirotaka Otachic, Yota Uehara, Ryuhei Yamada, Takeshi MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Brown Univ Dept Comp Sci Providence RI 02912 USA Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan JST CREST Kawaguchi Saitama 3320012 Japan Kyushu Univ Fac Econ Higashi Ku Fukuoka 8128581 Japan

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.

关键词： Combinatorial reconfiguration graph algorithm Independent set Sliding token Tree

来源：评论

学校读者我要写书评

暂无评论

Note on property M(k) of some complete multipartite graphs

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 228-231页

作者： Wang, Yanning Wang, Yanyan Zhang, Xuguang Yanshan Univ Sch Sci Qinhuangdao Hebei Peoples R China Yanshan Univ Sch Elect Engn Key Lab Ind Comp Control Engn Hebei Prov Qinhuangdao Hebei Peoples R China Yanshan Univ Sch Econ & Management Qinhuangdao Hebei Peoples R China

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.

关键词： List coloring Property M(k) Complete multipartite graphs graph algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for GA-H reduced graphs

引用

JOURNAL OF DISCRETE algorithmS 2015年 35卷 17-26页

作者： Gavril, Fanica Technion Dept Comp Sci IL-32000 Haifa Israel

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.

关键词： graph algorithm GA-H reduced graph H-mixed graph Subgraph overlap graph Subtree filament graph Maximum independent set

来源：评论

学校读者我要写书评

暂无评论

Fast and Scalable NUMA-based Thread Parallel Breadth-first Search 13

Fast and Scalable NUMA-based Thread Parallel Breadth-first S...

引用

International Conference on High Performance Computing and Simulation (HPCS)

作者： Yasui, Yuichiro Fujisawa, Katsuki Kyushu Univ Nishi Ku 744 Motooka Fukuoka 812 Japan JST COI Nishi Ku Fukuoka Japan JST CREST Nishi Ku Fukuoka Japan

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).

关键词： Breadth-first search graph algorithm parallel algorithm NUMA-aware graph500 benchmark

来源：评论

学校读者我要写书评

暂无评论

Fast Sparse Matrix and Sparse Vector Multiplication algorithm on the GPU 29

Fast Sparse Matrix and Sparse Vector Multiplication Algorith...

引用

29th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Yang, Carl Wang, Yangzihao Owens, John D. Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA

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.

关键词： parallel GPU graph algorithm sparse matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Divide & Conquer: I/O Efficient Depth-First Search 15

Divide & Conquer: I/O Efficient Depth-First Search

引用

ACM SIGMOD International Conference on Management of Data

作者： Zhang, Zhiwei Yu, Jeffrey Xu Qin, Lu Shang, Zechao Chinese Univ Hong Kong Hong Kong Peoples R China Univ Technol FEIT Ctr QCIS Sydney NSW Australia

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.

关键词： graph algorithm I/O Efficient Depth-first Search

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：