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

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Li, Jason Panigrahi, Debmalya Carnegie Mellon Univ Pittsburgh PA 15213 USA Duke Univ Durham NC USA

ISBN: (纸本)9781450380539

The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting s - t mincuts (and by duality, the values of s - t maxflows) for all pairs of vertices s and t in an undirected graph. Gomory and Hu showed that it can be computed using n - 1 exact maxflow computations. Surprisingly, this remains the best algorithm for Gomory-Hu trees more than 50 years later, even for approximate mincuts. In this paper, we break this longstanding barrier and give an algorithm for computing a (1 + epsilon)-approximate Gomory-Hu tree using polylog(n) maxflow computations. Specifically, we obtain the runtime bounds we describe below. We obtain a randomized (Monte Carlo) algorithm for undirected, weighted graphs that runs in (O) over tilde (m + n(3/2)) time and returns a (1 + epsilon)-approximate Gomory-Hu tree algorithm whp. Previously, the best running time known was (O) over tilde (n(5/2)), which is obtained by running Gomory and Hu's original algorithm on a cut sparsifier of the graph. Next, we obtain a randomized (Monte Carlo) algorithm for undirected, unweighted graphs that runs in m(4/3+o(1)) time and returns a (1 + epsilon)-approximate Gomory-Hu tree algorithm whp. This improves on our first result for sparse graphs, namely m = o(n(9/8)). Previously, the best running time known for unweighted graphs was (O) over tilde (mn) for an exact Gomory-Hu tree (Bhalgat et al., STOC 2007);no better result was known if approximations are allowed. As a consequence of our Gomory-Hu tree algorithms, we also solve the (1 + epsilon)-approximate all pairs mincut (APMC) and single source mincut (SSMC) problems in the same time bounds. (These problems are simpler in that the goal is to only return the s - t mincut values, and not the mincuts.) This improves on the recent algorithm for these problems in (O) over tilde (n(2)) time due to Abboud et al. (FOCS 2020).

关键词： graph algorithm Gomory-Hu tree graph connectivity

来源：评论

学校读者我要写书评

暂无评论

I/O-Efficient algorithms for Topological Sort and Related Problems

引用

ACM TRANSACTIONS ON algorithmS 2022年第1期18卷 5-5页

作者： Cao, Nairen Fineman, Jeremy T. Russell, Katina Yang, Eugene Georgetown Univ Dept Comp Sci St Marys Hall37th & O St NW Washington DC 20057 USA

This article presents I/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graph G = (V, E). Both algorithms are randomized and have I/O-costs O(sort (E) center dot poly(log V)), with high probability, where sort (E) = O(E/B log(M/B) (E/B)) is the I/O cost of sorting an |E|-element array on a machine with size-B blocks and size-M cache/internal memory. These are the first algorithms for these problems that do not incur at least one I/O per vertex, and as such these are the first I/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs.

关键词： I/O efficient graph algorithm topological sort external memory strongly connected components

来源：评论

学校读者我要写书评

暂无评论

Partitioning vertices into in- and out-dominating sets in digraphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 285卷 43-54页

作者： Nakamura, Kosuke Araki, Toru Gunma Univ Div Elect & Informat Kiryu Gunma 3768515 Japan

For a connected graph, it is known that there exists a partition of the vertex set into two dominating sets of the graph. However, for a digraph, there does not always exist such partition of the vertex set. We consider the problem of determining whether there is a partition of the vertex set into in- and out-dominating sets of the digraph. In this paper, we obtain the following results: (1) The decision problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a polynomial time algorithm for deciding the existence of such partition. (C) 2020 Elsevier B.V. All rights reserved.

关键词： graph algorithm Domination Digraph In-domination Out-domination Domatic partition

来源：评论

学校读者我要写书评

暂无评论

Complexity of the multi-service center problem

引用

THEORETICAL COMPUTER SCIENCE 2020年 842卷 18-27页

作者： Ito, Takehiro Kakimura, Naonori Kobayashi, Yusuke Tohoku Univ Sendai Miyagi Japan Keio Univ Tokyo Japan Kyoto Univ Kyoto Japan

The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Facility location graph algorithm Multi-service location

来源：评论

学校读者我要写书评

暂无评论

graphLib: A Parallel graph Mining Library for Joint Cloud Computing

GraphLib: A Parallel Graph Mining Library for Joint Cloud Co...

引用

IEEE International Conference on Joint Cloud Computing (JCC)

作者： Zhang, Kai Fang, Yange Zheng, Yingying Zeng, Hongbin Xu, Lijie Wang, Wei Chinese Acad Sci State Key Lab Comp Sci Inst Software Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

ISBN: (纸本)9781728169811

graph algorithms are widely applied in social networks, computational biology, Internet security and a broad range of complexity science. Although there are many state-of-the-art graph frameworks, few frameworks support parallel graph mining in joint cloud computing environment. In this paper, we propose graphLib, a parallel graph mining library, based on a BSP (Bulk Synchronous Parallel) service over joint cloud computing which was proposed in our prior work. We first summarize the features of commonly-used graph mining algorithms, and present our approaches for parallelizing typical graph mining algorithms. graphLib includes 17 parallel graph mining algorithms that can be used in 3 scenarios. We evaluate the performance of 4 typical parallel graph algorithms in graphLib on three real-world datasets. Our parallelized algorithms can achieve sub-linear scalability.

关键词： graph algorithm BSP JointCloud

来源：评论

学校读者我要写书评

暂无评论

Performance Evaluation of Fault Tolerant Routing algorithm in Data Center Networks 7th

Performance Evaluation of Fault Tolerant Routing Algorithm i...

引用

7th International Symposium on Security and Privacy in Social Networks and Big Data, SocialSec 2021

作者： Liu, Ningning Fan, Weibei Fan, Jianxi Suzhou Vocational University Suzhou215104 China Nanjing University of Posts and Telecommunications Nanjing210003 China Soochow University Suzhou215031 China

ISBN: (纸本)9789811679124

Nowdays, the vigorous development of cloud computing technology has brought great changes to the development of the whole information industry. The traditional data center network topology construction method and the operation mechanism of the network layer control plane are solidified, which have been difficult to meet the increasing demand for high performance and high cost performance under the new situation. Researchers map the topology of the data center network to an undirected graph, and use graph algorithms to implement fault-tolerant routing in complex networks. However, the shortest path algorithm of some early graphs cannot be applied to all topological graphs. In this paper, we analyze the advantages and disadvantages of related algorithms, and propose a fault-tolerant routing algorithm for all networks, which can dynamically call different algorithms according to the current number of nodes and links. The experimental results show that it can effectively improve the accuracy and fault tolerance of the algorithm and reduce the consumption of time and memory. © 2021, Springer Nature Singapore Pte Ltd.

关键词： Data center network Fault tolerant routing graph algorithm Performance evaluation

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of independent set reconfiguration problems

引用

DISCRETE APPLIED MATHEMATICS 2020年 283卷 336-345页

作者： Ito, Takehiro Kaminski, Marcin Ono, Hirotaka Suzuki, Akira Uehara, Ryuhei Yamanaka, Katsuhisa Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan Univ Warsaw Dept Math Comp Sci & Mech Banacha 2 PL-02097 Warsaw Poland Nagoya Univ Grad Sch Informat Chikusa Ku Furocho Nagoya Aichi 4648601 Japan JAIST Sch Informat Sci Asahidai 1-1 Nomi Ishikawa 9231292 Japan Iwate Univ Fac Sci & Engn Ueda 4-3-5 Morioka Iwate 0208551 Japan

Suppose that we are given two independent sets I-0 and I-r of a graph such that vertical bar I-0 vertical bar = vertical bar I-r vertical bar, and imagine that a token is placed on each vertex in I-0. Then, the token jumping problem is to determine whether there exists a sequence of independent sets which transforms I-0 into I-r so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is PSPACE-complete even for planar graphs with maximum degree three. In this paper, we first show that the problem is W[1]-hard when parameterized only by the number of tokens. We then give an FPT algorithm for general graphs when parameterized by both the number of tokens and the maximum degree. Our FPT algorithm can be modified so that it finds an actual sequence of independent sets between I-0 and I-r with the minimum number of token movements. We finally show that one of the results for token jumping can be extended to a more generalized reconfiguration problem for independent sets, called TOKEN ADDITION AND REMOVAL. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration Fixed parameter tractability graph algorithm Independent set

来源：评论

学校读者我要写书评

暂无评论

On Coloring Rectangular and Diagonal Grid graphs for Multipatterning and DSA Lithography

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2020年第6期39卷 1205-1216页

作者： Guo, Daifeng Zhang, Hongbo Wong, Martin D. F. Univ Illinois Dept Elect & Comp Engn Champaign IL 61801 USA Facebook Inc Dept Engn Menlo Pk CA 94025 USA

Rectangular grid graph (RGG) and diagonal grid graph (DGG) are induced subgraphs of a rectangular or diagonal grid, respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multipatterning lithography (MPL). However, the problem in general is computationally difficult for k > 2, while it remains an open question on grid graphs due to their regularity and sparsity. On the other hand, directed self-assembly (DSA) technique can work with MPL to optimize the graph by grouping neighboring vertices such that k can be reduced, but the problem of deploying the grouping for coloring is even more intractable. In this paper, we study both of the k-coloring problems, with and without DSA grouping, on RGG and DGG. Without grouping, a complete k-coloring analysis is conducted and particularly the NP-completeness of 3-coloring on a diagonal grid is proved. When considering grouping, we present a 3-coloring solution and prove the NP-completeness to solve the problem of k = 2.

关键词： Design for manufacturing (DFM) directed self-assembly (DSA) graph algorithm grid graph k-coloring multiple patterning lithography (MPL)

来源：评论

学校读者我要写书评

暂无评论

LOCAL FLOW PARTITIONING FOR FASTER EDGE CONNECTIVITY

引用

SIAM JOURNAL ON COMPUTING 2020年第1期49卷 1-36页

作者： Henzinger, Monika Rao, Satish Wang, Di Univ Vienna A-1090 Vienna Austria Univ Calif Berkeley Comp Sci Div Berkeley CA 94720 USA Georgia Inst Technol Atlanta GA 30332 USA

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log(2) n log log(2) n) time algorithm. This improves on both the best previously known deterministic running time of O(m log(12) n) (Kawarabayashi and Thorup [J. ACM, 66 (2018), 41) and the best previously known randomized running time of O(m log(3) n) (Karger [J. ACM, 47 (2000), pp. 46-761) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow-and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest.

关键词： min cut graph algorithm deterministic algorithm flow edge connectivity local algorithm

来源：评论

学校读者我要写书评

暂无评论

Characterizing Star-PCGs

引用

algorithmICA 2020年第10期82卷 3066-3090页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, d min, d max) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d min = d max such that G has an edge between two vertices u, v. V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [d min, d max]. The tree T is also called a witness tree of the PCG G. How to recognize PCGs is a wide-open problem in the literature. This paper gives a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

关键词： Pairwise compatibility graph Polynomial-time algorithm graph algorithm graph theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：