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

Minimum cost source location problem with local 3-vertex-connectivity requirements

THEORETICAL COMPUTER SCIENCE 2007年第1期372卷 81-93页

作者： Ishii, Toshimasa Fujita, Hitoshi Nagamochi, Hiroshi Otaru Univ Dept Informat & Management Sci Otaru Hokkaido 0478501 Japan Matsushita Syst & Technol Co Ltd Osaka 5406321 Japan Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v E V has a demand d(V) epsilon Z(+) and a cost c(v) epsilon R+, where Z(+) and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G requires finding a set S of vertices minimizing Sigma(v epsilon S) c(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v epsilon V - S. It is known that if there exists a vertex v epsilon V with d(v) >= 4, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(vertical bar V vertical bar(4) log(2) vertical bar V vertical bar) time if d(v) <= 3 holds for each vertex v epsilon V. (c) 2006 Elsevier B.V. All rights reserved.

关键词： graph algorithm undirected graph location problem local vertex-connectivity polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for graphs with small octopus

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期134卷 105-128页

作者： Fomin, FV Kratsch, D Müller, H Univ Bergen Dept Informat N-5020 Bergen Norway Univ Metz Lab Informat Theor & Appliquee F-57045 Metz 01 France Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England

A d-octopus of a graph G = (V, E) is a subgraph T = (W, F) of G such that W is a dominating set of G, and T is the union of d (not necessarily disjoint) shortest paths of G that have one endpoint in common. First, we study the complexity of finding and approximating a d-octopus of a graph. Then we show that for some NP-complete graph problems that are hard to approximate in general there are efficient approximation algorithms with worst case performance ratio c . d for some small constant c > 0 (depending on the problem) assuming that the input graph G is given together with a d-octopus of G. For example, there is a linear time algorithm to approximate the bandwidth of a graph within a factor of 8d. Furthermore, the minimum number of subsets in a partition of the vertex set of a graph into clusters of diameter at most k can be approximated in linear time within a factor of 3d (for k = 2) and 2d (for k greater than or equal to 3). Finally, we show that there are O(n(7d+2)) time algorithms to compute a minimum cardinality dominating set, respectively, total dominating set for graphs having a d-octopus. (C) 2003 Elsevier B.V. All rights reserved.

关键词： approximation algorithm graph algorithm bandwidth clustering lambda-coloring bilateral orientation domination

来源：评论

学校读者我要写书评

暂无评论

Computing Directed Pathwidth in O(1.89ⁿ) Time

引用

algorithmICA 2016年第1期75卷 138-157页

作者： Kitsunai, Kenta Kobayashi, Yasuaki Komuro, Keita Tamaki, Hisao Tano, Toshihiro Meiji Univ Dept Comp Sci Kawasaki Kanagawa Japan Gakushuin Univ Ctr Comp Toshima Ku Tokyo 171 Japan

We give an algorithm for computing the directed pathwidth of a digraph with n vertices in O(1.89(n)) time. This is the first algorithm with running time better than the straightforward O*(2(n)). As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in O(1.9657(n)) time.

关键词： Exact exponential algorithm graph algorithm Pathwidth

来源：评论

学校读者我要写书评

暂无评论

Solving String Problems on graphs Using the Labeled Direct Product

引用

algorithmICA 2022年第10期84卷 3008-3033页

作者： Rizzo, Nicola Tomescu, Alexandru, I Policriti, Alberto Univ Helsinki Dept Comp Sci Helsinki Finland Univ Udine Dept Math Comp Sci & Phys Udine Italy

Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching, longest common substring, matching statistics, and longest repeated substring. Recent lines of research focused on extending some of these problems to vertex-labeled graphs, either by using efficient ad-hoc approaches which do not generalize to all input graphs, or by indexing difficult graphs and having worst-case exponential complexities. In the absence of an ubiquitous and polynomial tool like the suffix tree for labeled graphs, we introduce the labeled direct product of two graphs as a general tool for obtaining optimal algorithms in the worst case: we obtain conceptually simpler algorithms for the quadratic problems of string matching (SMLG) and longest common substring (LCSP) in labeled graphs. Our algorithms run in time linear in the size of the labeled product graph, which may be smaller than quadratic for some inputs, and their run-time is predictable, because the size of the labeled direct product graph can be precomputed efficiently. We also solve LCSP on graphs containing cycles, which was left as an open problem by Shimohira et al. in 2011. To show the power of the labeled product graph, we also apply it to solve the matching statistics (MSP) and the longest repeated string (LRSP) problems in labeled graphs. Moreover, we show that our (worst-case quadratic) algorithms are also optimal, conditioned on the Orthogonal Vectors Hypothesis. Finally, we complete the complexity picture around LRSP by studying it on undirected graphs.

关键词： Longest repeated substring Longest common substring String algorithm graph algorithm Motif discovery Fine-grained complexity

来源：评论

学校读者我要写书评

暂无评论

An 8-approximation algorithm for L(2,1)-labeling of unit disk graphs

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期341卷 93-101页

作者： Ono, Hirotaka Yamanaka, Hisato Nagoya Univ Grad Sch Informat Dept Math Informat Chikusa ku Nagoya Aichi 4648601 Japan Kozo Keikaku Engn Inc 4-5-3 Chuo Nakano ku Tokyo 1640011 Japan

Given a graph G = (V, E), an L(2, 1)-labeling of the graph is an assignment l from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), vertical bar l(u) - l(v)vertical bar >= 2 if u and v are adjacent, and l(u) not equal l(v) if u and v are at distance 2. The L(2, 1)-labeling problem is to minimize the range of l (i.e., max(u is an element of V)(l(u))-min(u is an element of V)(l(u))+ 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L(2, 1)-labeling of unit disk graphs. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Frequency/channel assignment graph algorithm Distance-constrained labeling L(2,1)-labeling Approximation algorithm Unit disk graph

来源：评论

学校读者我要写书评

暂无评论

An efficient exact algorithm for constraint bipartite vertex cover

引用

JOURNAL OF algorithmS-COGNITION INFORMATICS AND LOGIC 2001年第2期38卷 374-410页

作者： Fernau, H Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

The constraint bipatite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k(1), k(2), is there a vertex cover taking at most k(1) vertices from one and at most k(2) vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999(k1+k2) + (k(1) + k(2))n) time. Our algorithm is efficient and practical for small values of k(1) and k(2), as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed;nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths land hence the depth of the search tree as a whole) by a sort of bonus points. (C) 2001 academic Press.

关键词： NP-complete problem graph algorithm VLSI vertex cover fixed parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving path problems on the GPU

引用

PARALLEL COMPUTING 2010年第5-6期36卷 241-253页

作者： Buluc, Aydin Gilbert, John R. Budak, Ceren Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

We consider the computation of shortest paths on graphic Processing Units (GPUs). The blocked recursive elimination strategy we use is applicable to a class of algorithms (such as all-pairs shortest-paths, transitive closure, and LU decomposition without pivoting) having similar data access patterns. Using the all-pairs shortest-paths problem as an example, we uncover potential gains over this class of algorithms. The impressive computational power and memory bandwidth of the CPU make it an attractive platform to run such computationally intensive algorithms. Although improvements over CPU implementations have previously been achieved for those algorithms in terms of raw speed, the utilization of the underlying computational resources was quite low. We implemented a recursively partitioned all-pairs shortest-paths algorithm that harnesses the power of GPUs better than existing implementations. The alternate schedule of path computations allowed us to cast almost all operations into matrix-matrix multiplications on a semiring. Since matrix-matrix multiplication is highly optimized and has a high ratio of computation to communication, our implementation does not suffer from the premature saturation of bandwidth resources as iterative algorithms do. By increasing temporal locality, our implementation runs more than two orders of magnitude faster on an NVIDIA 8800 CPU than on an Opteron. Our work provides evidence that programmers should rethink algorithms instead of directly porting them to CPU. (C) 2009 Elsevier By. All rights reserved.

关键词： All-pairs shortest-paths Gaussian elimination graphical processing unit Semiring Matrix multiplication graph algorithm Shortest path Linear algebra

来源：评论

学校读者我要写书评

暂无评论

Global total k-domination: Approximation and hardness results

引用

THEORETICAL COMPUTER SCIENCE 2021年 850卷 1-19页

作者： Panda, B. S. Goyal, Pooja Indian Inst Technol Delhi Dept Math New Delhi 110016 India

A subset D subset of V of a graph G = (V, E) is called a global total k-dominating set of G if D is a total k-dominating set of both G and the complement (G) over bar of G. The MINIMUM GLOBAL TOTAL k-DOMINATION problem is to find a global total k-dominating set of minimum cardinality of the input graph G and DECIDE GLOBAL TOTAL k-DOMINATION problem is the decision version of MINIMUM GLOBAL TOTAL k-DOMINATION problem. The DECIDE GLOBAL TOTAL k-DOMINATION problem is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen the NP-completeness result of DECIDE GLOBAL TOTAL k-DOMINATION problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs, star-convex bipartite graphs and doubly chordal graphs. On the positive side, we give a polynomial time algorithm for the MINIMUM GLOBAL TOTAL k-DOMINATION problem for chordal bipartite graphs, which is a subclass of bipartite graphs. We propose a 2(1 +ln vertical bar V vertical bar)-approximation algorithm for the MINIMUM GLOBAL TOTAL k-DOMINATION problem for any graph. We show that MINIMUM GLOBAL TOTAL k-DOMINATION problem cannot be approximated within (1 - epsilon)ln vertical bar V vertical bar for any epsilon > 0 unless P = NP for any integer k >= 1. We further show that for bipartite graphs, MINIMUM GLOBAL TOTAL k DOMINATION problem cannot be approximated within (1/6 - c)ln vertical bar V vertical bar for any epsilon > 0 unless P = NP for any k >= 1. Finally, we show that the MINIMUM GLOBAL TOTAL k-DOMINATION problem is APX-complete for bounded degree bipartite graphs for any fixed integer k >= 1. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Domination Polynomial time algorithm NP-complete APX-complete graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Polymatroid-based capacitated packing of branchings

引用

DISCRETE APPLIED MATHEMATICS 2019年 270卷 190-203页

作者： Matsuoka, Tatsuya Szigeti, Zoltan NEC Corp Ltd Nakahara Ku 1753 Shimonumabe Kawasaki Kanagawa Japan Univ Grenoble Alpes CNRS Grenoble INP G SCOP 46 Ave Felix Viallet Grenoble France

Edmonds (1973) characterized the condition for the existence of a packing of spanning arborescences and also that of spanning branchings in a directed graph. Durand de Gevigney, Nguyen and Szigeti (2013) generalized the spanning arborescence packing problem to a matroid-based arborescence packing problem and gave a necessary and sufficient condition for the existence of a packing and a polynomial-time algorithm. In this paper, a generalization of this latter problem - the polymatroid-based arborescence packing problem - is considered. Two problem settings are formulated: an unsplittable version and a splittable version. The unsplittable version is shown to be strongly NP-complete. Whereas, the splittable version, which generalizes the capacitated version of the spanning arborescence packing problem, can be solved in strongly polynomial time. For convenience, we provide a strongly polynomial-time algorithm for the problem of the polymatroid-based capacitated packing of branchings for the splittable version. (C) 2019 Elsevier B.V. All rights reserved.

关键词： graph algorithm Arborescence packing Polymatroid Arc capacity

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：