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

Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph

引用

THEORETICAL COMPUTER SCIENCE 2022年 932卷 13-20页

作者： Hong, Weizhi Ran, Yingli Zhang, Zhao Zhejiang Normal Univ Jinhua Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China

In a minimum general partial dominating set problem (MinGPDS), given a graph G = ( V, E), a profit function p : V -> R+ and a threshold K, the goal is to find a minimum subset of vertices D subset of V such that the total profit of those vertices dominated by D is at least K(a vertex is dominated by D if it is either in D or has at least one neighbor in D). In a maximum general budgeted dominating set problem (MaxGBDS), given a budget B, the goal is to find a vertex set D with at most B vertices such that the total profit of those vertices dominated by D is as large as possible. We present the first parallel algorithms for MinGPDS and MaxGBDS in unit disk graphs. They both run in O(logn) rounds on O(n) machines, and achieve constant approximation ratios. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Partial dominating set Budgeted dominating set unit disk graph Parallel algorithm Approximation ratio

来源：评论

学校读者我要写书评

暂无评论

Parallel Algorithm for Minimum Partial Dominating Set in unit disk graph 15th

Parallel Algorithm for Minimum Partial Dominating Set in Uni...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Hong, Weizhi Zhang, Zhao Ran, Yingli Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China

ISBN: (纸本)9783030926816;9783030926809

In this paper, we consider the minimum partial dominating set problem in unit disk graphs (MinPDS-UD). Given a set of points V on the plane with vertical bar V vertical bar = n, two points in V are adjacent in the unit disk graph if their Euclidean distance is no larger than one unit length. A point dominates itself and all its neighboring points. For an integer k <= n, the goal of MinPDS-UD is to find a minimum subset of points D subset of V such that at least k points are dominated by D. We present the first parallel algorithm for MinPDS-UD. It runs in O(log n) rounds on O(n) machines, and achieves a constant approximation ratio.

关键词： Partial dominating set unit disk graph Parallel algorithm Approximation ratio

来源：评论

学校读者我要写书评

暂无评论

Faster approximation for maximum independent set on unit disk graph

引用

INFORMATION PROCESSING LETTERS 2017年 127卷 58-61页

作者： Nandy, Subhas C. Pandit, Supantha Roy, Sasanka Indian Stat Inst Kolkata India

Maximum independent set from a given set D of unit disks intersecting a horizontal line can be solved in O (n(2)) time and O (n(2)) space. As a corollary, we design a factor 2 approximation algorithm for the maximum independent set problem on unit disk graph which takes both time and space of O (n(2)). The best known factor 2 approximation algorithm for this problem runs in O (n(2) logn) time and takes O (n(2)) space [1,2]. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Approximation algorithms Computational geometry Maximum independent set unit disk graph Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

A Simpler Method to Obtain a PTAS for Connected k-Path Vertex Cover in unit disk graph 12th

A Simpler Method to Obtain a PTAS for Connected <i>k</i>-Pat...

引用

12th International Conference on Wireless Algorithms, Systems, and Applications (WASA)

作者： Zhang, Zhao Huang, Xiaohui Chen, Lina Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China Zhejiang Normal Univ Lib & Informat Ctr Jinhua 321004 Zhejiang Peoples R China

ISBN: (纸本)9783319600338;9783319600321

Given a connected graph G = (V, E), a connected k-path vertex cover (CVCPk) is a vertex set C subset of V which contains at least one vertex from every path of G on k vertices and the subgraph of G induced by C is connected. This paper presents a new PTAS for Min-CVCPk on unit disk graphs. Compared with previous PTAS given by Liu et al., Our method not only simplifies the algorithm but also simplifies the analysis by a large amount.

关键词： Connected k-path vertex cover unit disk graph PTAS Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Algorithm for Maximum Independent Set on unit disk graph 2nd

Improved Algorithm for Maximum Independent Set on Unit Disk ...

引用

2nd Conference on Algorithms and Discrete Applied Mathematics (CALDAM)

作者： Jallu, Ramesh K. Das, Guatam K. Indian Inst Technol Dept Math Gauhati India

ISBN: (纸本)9783319292212;9783319292205

In this paper, we present a 2-factor approximation algorithm for the maximum independent set problem on a unit disk graph, where the geometric representation of the graph has been given. We use dynamic programming and farthest point Voronoi diagram concept to achieve the desired approximation factor. Our algorithm runs in O(n(2) log n) time and O(n(2)) space, where n is the input size. We also propose a polynomial time approximation scheme (PTAS) for the same problem. Given a positive integer k, it can produce a solution of size 1/(1+ 1/k)(2) vertical bar OPT vertical bar in n O(k) time, where vertical bar OPT vertical bar is the optimum size of the solution. The best known algorithm available in the literature runs in (i) O(n(3)) time and O(n(2)) space for 2-factor approximation, and (ii) n(O(k log k)) time for PTAS [Das, G. K., De, M., Kolay, S., Nandy, S. C., Sur-Kolay, S.: Approximation algorithms for maximum independent set of a unit disk graph. Information Processing Letters 115(3), 439-446 (2015)].

关键词： Maximum independent set unit disk graph Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for maximum independent set of a unit disk graph

引用

INFORMATION PROCESSING LETTERS 2015年第3期115卷 439-446页

作者： Das, Gautam K. De, Minati Kolay, Sudeshna Nandy, Subhas C. Sur-Kolay, Susmita Indian Inst Technol Guwahati Dept Math Gauhati India Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Inst Math Sci Madras 600113 Tamil Nadu India Indian Stat Inst Kolkata India

We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n(3)) and O(n(2)), respectively. For a penny graph, our proposed 2-approximation algorithm works in O(n logn) time using O(n) space. We also propose a polynomial-time approximation scheme (PTAS) for the maximum independent set problem for a unit disk graph. Given an integer k > 1, it produces a solution of size 1/(1+1/k)(2) vertical bar OPT vertical bar in O(k(4)n(sigma k) (logk) + nlogn) time and O(n + klogk) space, where OPT is the subset of disks in an optimal solution and ak sigma k <= 2. For a penny graph, the proposed PTAS produces a solution of size 1/(1+1/k) vertical bar OPT vertical bar in O(2(2 sigma k)nk + nlogn) time using O(2(2 sigma k)+n) space. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Maximum independent set unit disk graph Approximation algorithms PTAS Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Contraction Decomposition in unit disk graphs and Algorithmic Applications in Parameterized Complexity

引用

ACM TRANSACTIONS ON ALGORITHMS 2024年第2期20卷 1-50页

作者： Panolan, Fahad Saurabh, Saket Zehavi, Meirav Indian Inst Technol IIT Dept Comp Sci & Engn Hyderabad India HBNI Inst Math Sci Theoret Comp Sci Grp Chennai Tamil Nadu India Univ Bergen Algorithms Grp Bergen Norway Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

We give a new decomposition theorem in unit disk graphs ( UDGs) and demonstrate its applicability in the fields of Structural graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits an "almost" Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010], and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, and therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi (***/watch?v=2Bq2gy1N01w) regarding the existence of contraction decompositions for classes of graphs beyond H-minor free graphs though under a relaxation of the original formulation. Second, we present a "parameteric version" of our new decomposition theorem. We prove that there is an algorithm that, given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of O(k) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into O(k) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece that is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or sligh

关键词： Parameterized complexity contraction decomposition unit disk graph Min bisection

来源：评论

学校读者我要写书评

暂无评论

Total (restrained) domination in unit disk graphs

引用

INFORMATION AND COMPUTATION 2024年 300卷

作者： Yang, Yu Wang, Cai-Xia Xu, Shou-Jun Lanzhou Univ Sch Math & Stat Gansu Key Lab Appl Math & Complex Syst Lanzhou 730000 Gansu Peoples R China Minnan Normal Univ Sch Math & Stat Zhangzhou 363000 Fujian Peoples R China

The minimum total domination problem and the minimum total restrained domination problem are classical combinatorial optimization problems. In this paper, we first show that the decision versions of both the minimum total domination problem and the minimum total restrained domination problem are NP-complete for grid graphs (a subclass of unit disk graphs), thereby strengthening the result on the total domination decision problem in unit disk graphs established by Jena et al. (2021). Then, we present a linear-time 6.387approximation algorithm for the minimum total domination problem in unit disk graphs, improving upon the previous algorithm with a ratio of 8 by Jena et al. (2021). Finally, we propose a linear-time 10.387-approximation algorithm and a PTAS for the minimum total restrained domination problem in unit disk graphs. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Total dominating set Total restrained dominating set unit disk graph NP-complete Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Sparse hop spanners for unit disk graphs

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2022年 100卷 101808-101808页

作者： Dumitrescu, Adrian Ghosh, Anirban Toth, Csaba D. Algoresearch LLC Milwaukee WI USA Univ North Florida Sch Comp Jacksonville FL 32224 USA Calif State Univ Northridge Dept Math Los Angeles CA USA Tufts Univ Dept Comp Sci Medford MA 02155 USA

A unit disk graph G on a given set P of points in the plane is a geometric graph where an edge exists between two points p, q is an element of P if and only if vertical bar pq vertical bar <= 1. A spanning subgraph G' of G is a k hop spanner if and only if for every edge pq is an element of G, there is a path between p, q in G' with at most k edges. We obtain the following results for unit disk graphs in the plane. (i) Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. (ii) Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. (iii) Every n-vertex unit disk graph has a 2-hop spanner with O (n log n) edges. This is the first nontrivial construction of 2-hop spanners. (iv) For every sufficiently large positive integer n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known. (v) For every finite point set on a circle, there exists a plane (i.e., crossing-free) 4-hop spanner. As such, this provides a tight bound for points on a circle. (vi) The maximum degree of k-hop spanners cannot be bounded from above by a function of k for any positive integer k. (C) 2021 Elsevier B.V. All rights reserved.

关键词： graph approximation epsilon-net Hop-spanner unit disk graph Lower bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：