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

A fully dynamic approximation scheme for shortest paths in planar graphs

algorithmICA 1998年第3期22卷 235-249页

作者： Klein, PN Subramanian, S Brown Univ Providence RI 02912 USA

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter epsilon such that 0 < epsilon, our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1 + epsilon factor. The time bounds for both query and update for our algorithm is O (epsilon(-1) n(2/3) log(2) n log D), where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph.

关键词： dynamic algorithm graph algorithm shortest path minimum-cost path planar graph

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Augmenting Edge-Connectivity between Vertex Subsets

引用

algorithmICA 2014年第1期69卷 130-147页

作者： Ishii, Toshimasa Makino, Kazuhisa Hokkaido Univ Grad Sch Econ Sapporo Hokkaido 0600809 Japan Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan

Given a directed or undirected graph G=(V,E), a collection of two disjoint subsets of V, and a requirement function , we consider the problem (called area-to-area edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph satisfies for all XaS dagger V, with SaS dagger XaS dagger V-T, where d (G) (X) denotes the degree of a vertex set X in G. This problem can be regarded as a natural generalization of the global, local, and node-to-area edge-connectivity augmentation problems. In this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of , unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation. We also provide an -approximation algorithm for the area-to-area edge-connectivity augmentation problem, which is a natural extension of Kortsarz and Nutov's algorithm (Kortsarz and Nutov, J. Comput. Syst. Sci., 74:662-670, 2008). This together with the negative result implies that the problem is -approximable, unless P=NP, which solves open problems for node-to-area edge-connectivity augmentation in Ishii et al. (algorithmica, 56:413-436, 2010), Ishii and Hagiwara (Discrete Appl. Math., 154:2307-2329, 2006), Miwa and Ito (J. Oper. Res. Soc. Jpn., 47:224-243, 2004). Furthermore, we characterize the node-to-area and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and k-modulotone functions.

关键词： graph algorithm Approximation algorithm Edge-connectivity Modulotone function

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Cop-robber guarding game with cycle robber-region

引用

THEORETICAL COMPUTER SCIENCE 2011年第4-5期412卷 383-390页

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

A cop-robber guarding game is played by the robber-player and the cop-player on a graph G with a partition R and C of the vertex set. The robber-player starts the game by placing a robber (her pawn) on a vertex in R, followed by the cop-player who places a set of cops (her pawns) on some vertices in C. The two players take turns in moving their pawns to adjacent vertices in G. The cop-player moves the cops within C to prevent the robber-player from moving the robber to any vertex in C. The robber-player wins if it gets a turn to move the robber onto a vertex in C on which no cop situates, and the cop-player wins otherwise. The problem is to find the minimum number of cops that admits a winning strategy to the cop-player. It has been shown that the problem is polynomially solvable if R induces a path, whereas it is NP-complete if R induces a tree. In this paper, we show that the problem remains NP-complete even if R induces a 3-star and that the problem is polynomially solvable if R induces a cycle. (c) 2010 Elsevier B.V. All rights reserved.

关键词： Pursuit-evasion games graph algorithm Path covering NP-complete Cop-robber game

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：