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

A linear algorithm for semi-external cutnode computation

INFORMATION SCIENCES 2022年 615卷 368-384页

作者： Wan, Xiaolong Wang, Hongzhi Harbin Inst Technol Sch Comp Sci & Technol Harbin Peoples R China

In the literature, many algorithms have been proposed for finding cutnodes on undirected graphs, since cutnodes are crucial to graph connectivity. Here, a cutnode of an undirected graph G is a node of G, whose deletion will cause a reachable pair of the other nodes in G to be unreachable. Currently, the difficulty of maintaining the entire G in the main memory makes researchers pay attention to compute cutnodes on semi-external memory model. This paper shows that traditional semi-external algorithms are limited by their unbounded time and I/O consumption, making them impractical when G is relatively large or complex. Thus, we propose a linear semi -external cutnode computation algorithm, named SECN. Assuming that G has n nodes and m edges, and B is the disk block size. SECN is the first that can find all the cutnodes of G in O(m thorn n) time and with O(m/B) I/O cost on the semi-external memory model, as far as we know. SECN also has a smaller minimum memory space requirement than traditional algorithms. Our experimental evaluation conducted on both synthetic and real graphs confirms that SECN significantly outperforms existing algorithms (up to 103 times faster). (c) 2022 Elsevier Inc. All rights reserved.

关键词： Cutnode Semi-external memory graph algorithm Linear algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for shortest cycles in undirected graphs

引用

INFORMATION PROCESSING LETTERS 2009年第10期109卷 493-498页

作者： Lingas, Andrzej Lundell, Eva-Marta Lund Univ Dept Comp Sci S-22100 Lund Sweden

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k + 2 for odd k, in time O(n(3/2) root log n). Thus, in general, it yields a 2 2/3 approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,...,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n(2) log n(log n + log M)). (C) 2009 Elsevier B.V. All rights reserved.

关键词： graph algorithm Approximation algorithm Shortest cycle Undirected graph Time complexity

来源：评论

学校读者我要写书评

暂无评论

An improved approximation algorithm for capacitated multicast routings in networks

引用

THEORETICAL COMPUTER SCIENCE 2008年第1期390卷 81-91页

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

Let G = (V, E) be a connected graph such that each edge e is an element of E is weighted by nonnegative real w(e). Let s be a vertex designated as a source, k be a positive integer, and S subset of V be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition {Z(1), Z(2), . . . , Z(l)} of S and a set {T-1, T-2, . . . , T-l} of trees of G such that Z(i) consists of at most k terminals and each Ti spans Z(i) boolean OR {s}. The objective is to minimize Sigma(l)(i=1) w(T-i), where w(T-i) denotes the sum of weights of all edges in T-i. In this paper, we propose a (3/2 + (4/3)rho)-approximation algorithm to the CMTR, where rho is the best achievable approximation ratio for the Steiner tree problem. (C) 2007 Elsevier B.V. All rights reserved.

关键词： approximation algorithm graph algorithm multicast routing problem network optimization tree cover

来源：评论

学校读者我要写书评

暂无评论

A heuristic approach for searching (d, n)-packing colorings of infinite lattices

引用

DISCRETE APPLIED MATHEMATICS 2019年 257卷 353-358页

作者： Korze, Danilo Markus, Ziga Vesel, Aleksander Univ Maribor Fac Elect Engn & Comp Sci Koroska Cesta 46 SI-2000 Maribor Slovenia Univ Maribor Fac Nat Sci & Math Koroska Cesta 160 SI-2000 Maribor Slovenia

A (d, n)-packing k-coloring of a graph G for integers d and n is a mapping from V(G) to the set {1, 2, ..., k} such that vertices with color i is an element of {1, 2, ..., k} have pairwise distance greater than d + left perpendicular i-1/n right perpendicular The smallest integer k for which there exists a (d, n)-packing coloring of a graph G is called the (d, n)-packing chromatic number of G. We propose a new heuristic approach to find (d, n)-packing colorings of infinite lattices. The proposed algorithms have been able to obtain several (d, n)-packing colorings of the infinite square, hexagonal, triangular, eight-regular and octagonal lattice. The obtained results improve upper bounds on the corresponding (d, n)-packing chromatic numbers for these graphs. (C) 2018 Published by Elsevier B.V.

关键词： graph algorithm Heuristic algorithm Packing coloring Infinite lattice

来源：评论

学校读者我要写书评

暂无评论

Efficient Semi-External SCC Computation

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第4期35卷 3794-3807页

作者： Wan, Xiaolong Wang, Hongzhi Harbin Inst Technol Sch Comp Sci & Technol Harbin 150001 Peoples R China

In literature, many algorithms are proposed to find strongly connected components (SCC) for directed graphs. Specifically, a SCC of a directed graph G is one of its maximal subgraphs, in which any two nodes are reachable to each other. Existing in-memory algorithms are efficient, and can find all the SCCs of G in a linear time, with respect to the size of G. Nevertheless, as the sizes of graphs grow rapidly in real applications, current efforts have been focused on semi-external algorithms. Existing semi-external algorithms maintain an in-memory sketch A of G, and gradually restructure A with their in-memory processes (IMP) until all the SCCs can be computed based on A. However, the I/O and CPU costs of existing algorithms are still high when G is relatively large. Thus, this paper proposes a new semi-external algorithm EP-SCC with a novel IMP EP-Reduction for finding all the SCCs of G efficiently. Extensive experiments are conducted on both synthetic and real graphs, in which WDC-2014 contains 1.7 billion nodes, and eu-2015 has over 91 billion edges. Experimental results confirm that EP-SCC significantly outperforms existing semi-external SCC algorithms.

关键词： Computational modeling Memory management Costs Directed graphs Optimization methods Arrays Vegetation Strongly connected component semi-external memory graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Generalized rainbow connectivity of graphs

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期555卷 35-42页

作者： Uchizawa, Kei Aoki, Takanori Ito, Takehiro Zhou, Xiao Yamagata Univ Grad Sch Sci & Engn Yonezawa Yamagata 9928510 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

Let C = {c(1), c(2), ..., c(k)} be a set of k colors, and let (l) over right arrow = (l(1), l(2), ..., l(k)) be a k-tuple of nonnegative integers l(1), l(2), ..., l(k). For a graph G = (V, E), let f : E -> C be an edgecoloringof G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is (l) over right arrow -rainbow connected if every two vertices of G have a path Pconnecting them such that the number of edges on P that are colored with c(j) is at most for each index j epsilon {1, 2, ..., k}. Given a k-tuple (l) over right arrow and an edge-colored graph, we study the problem of determining whether the edge-colored graph is (l) over right arrow -rainbow connected. In this paper, we first study the computational complexity of the problem with regard to certain graph classes: the problem is NP-complete even for cacti, while is solvable in polynomial time for trees. We then give an FPT algorithm for general graphs when parameterized by both k and l(max) = max{l(j) vertical bar 1 <= j <= k}. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Cactus Fixed parameter tractability graph algorithm Rainbow connectivity Tree

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring (non-spanning) arborescences

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期943卷 131-141页

作者： Ito, Takehiro Iwamasa, Yuni Kobayashi, Yasuaki Nakahata, Yu Otachi, Yota Wasa, Kunihiro Tohoku Univ Grad Sch Informat Sci Sendai Japan Kyoto Univ Grad Sch Informat Kyoto Japan Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Japan Nara Inst Sci & Technol Div Informat Sci Nara Japan Nagoya Univ Grad Sch Informat Nagoya Japan Hosei Univ Fac Sci & Engn Tokyo Japan

In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arborescences in a digraph, where an arborescence is a directed graph such that its underlying undirected graph forms a tree and all vertices have in-degree at most 1. Given two arborescences in a digraph, the goal of the problem is to determine whether there is a (reconfiguration) sequence of arborescences between the given arborescences such that each arborescence in the sequence can be obtained from the previous one by removing an arc and then adding another arc. We show that this problem can be solved in polynomial time, whereas the problem is PSPACE-complete when we restrict arborescences in a reconfiguration sequence to directed paths or relax to directed acyclic graphs. We also show that there is a polynomial-time algorithm for finding a shortest reconfiguration sequence between two spanning arborescences. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Clustering as a dual problem to colouring

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2022年第4期41卷 1-36页

作者： Ikica, Barbara Gabrovsek, Bostjan Povh, Janez Zerovnik, Janez Univ Ljubljana Fac Math & Phys Ljubljana Slovenia Inst Math Phys & Mech Ljubljana Slovenia Univ Ljubljana Fac Mech Engn Ljubljana Slovenia

An essential step towards gaining a deeper insight into intricate mechanisms underlying the formation and functioning of complex networks is extracting and understanding their building blocks encoded in the clustering structure. At its core, the problem of partitioning vertices into clusters may be regarded as a dual problem to vertex colouring and, as such, permitted us to leverage the Petford-Welsh colouring algorithm to devise a highly scalable decentralised heuristic approach to cluster detection. As long as the graph under scrutiny admits a fairly well-defined clustering structure per se, the modified Petford-Welsh algorithm tends to perform on a par with or even surpasses existing techniques.

关键词： graph algorithm Community detection The Petford-Welsh algorithm Simulated annealing Complex networks

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2018年第3期37卷 2965-3004页

作者： Gonzaga de Oliveira, Sanderson L. Bernardes, J. A. B. Chagas, G. O. Univ Fed Lavras Lavras Brazil

This paper is concerned with applying bandwidth and profile reduction reordering algorithms prior to computing an incomplete Cholesky factorization and using this as a preconditioner for the conjugate gradient method. Hundreds of reordering algorithms have been proposed to solve the problems of bandwidth and profile reductions since the mid-1960s. In previous publications, a large range of heuristics for bandwidth and/or profile reductions was reviewed. Based on this experience, 13 heuristics were selected as the most promising methods. These are evaluated in this paper along with a variant of the breadth-first search procedure that is proposed. Numerical results confirm the effectiveness of this modified reordering algorithm for linear systems derived from specific application areas. Moreover, the most promising heuristics for several application areas are identified when reducing the computational cost of the incomplete Cholesky-conjugate gradient method.

关键词： Bandwidth reduction Profile reduction Combinatorial optimization Heuristics Metaheuristics Reordering algorithms Sparse matrices Renumbering Ordering graph labeling Conjugate gradient method graph algorithm Sparse symmetric positive-definite linear systems Incomplete Cholesky factorization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：