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

A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter

THEORETICAL COMPUTER SCIENCE 2019年 770卷 69-78页

作者： Le, Hoang-Oanh Le, Van Bang Univ Rostock Inst Informat Rostock Germany

In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP complete even when restricted to bipartite graphs. It has been proved that MATCHING CUT is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d >= 3, MATCHING CUT is NP-complete in the class of graphs of diameter d. This resolves an open problem posed by Borowiecki and Jesse-Jozefczyk (2008) [6]. We then show that, for any fixed integer d >= 4, MATCHING CUT is NP-complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that MATCHING CUT is polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving MATCHING CUT in graphs of diameter 2. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Matching cut NP-hardness graph algorithm Computational complexity Dichotomy theorem Decomposable graph

来源：评论

学校读者我要写书评

暂无评论

algorithmic aspects of semitotal domination in graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 766卷 46-57页

作者： Henning, Michael A. Pandey, Arti Univ Johannesburg Dept Pure & Appl Math Auckland Pk ZA-2006 Johannesburg South Africa Indian Inst Technol Ropar Dept Math Nangal Rd Rupnagar 140001 Punjab India

For a graph G = (V, E), a set D subset of V is called a semitotal dominating set of G if D is a dominating set of G, and every vertex in D is within distance 2 of another vertex of D. The MINIMUM SEMITOTAL DOMINATION problem is to find a semitotal dominating set of minimum cardinality. Given a graph G and a positive integer k, the SEMITOTAL DOMINATION DECISION problem is to decide whether G has a semitotal dominating set of cardinality at most k. The SEMITOTAL DOMINATION DECISION problem is known to be NP-complete for general graphs. In this paper, we show that the SEMITOTAL DOMINATION DECISION problem remains NP-complete for planar graphs, split graphs and chordal bipartite graphs. We give a polynomial time algorithm to solve the MINIMUM SEMITOTAL DOMINATION problem in interval graphs. We show that the MINIMUM SEMITOTAL DOMINATION problem in a graph with maximum degree A admits an approximation algorithm that achieves the approximation ratio of 2+3ln(Delta+1), showing that the problem is in the class log-APX. We also show that the MINIMUM SEMITOTAL DOMINATION problem cannot be approximated within (1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless NP subset of DTIME (vertical bar V vertical bar(0(log log vertical bar v vertical bar))) Finally, we prove that the MINIMUM SEMITOTAL DOMINATION problem is APX-complete for bipartite graphs with maximum degree 4. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Domination Semitotal domination Bipartite graphs Chordal graphs Interval graphs graph algorithm NP-complete Approximation algorithm APX-complete

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of colorable sets in classes of perfect graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 772卷 111-122页

作者： Ito, Takehiro Otachi, Yota Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan Kumamoto Univ Fac Adv Sci & Technol Chuo Ku 2-39-1 Kurokami Kumamoto 8608555 Japan

A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (called a reconfiguration sequence) between two c-colorable sets in the same graph. This problem generalizes the well-studied INDEPENDENT SET RECONFIGURATION problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for FEEDBACK VERTEX SET RECONFIGURATION. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm Colorable set Perfect graph

来源：评论

学校读者我要写书评

暂无评论

Secure domination in cographs

引用

DISCRETE APPLIED MATHEMATICS 2019年 262卷 179-184页

作者： Araki, Toru Yamanaka, Ryo Gunma Univ Div Elect & Informat Kiryu Gunma 3768515 Japan

A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex u is not an element of S, there is a vertex v is an element of S such that uv is an edge and (S \ {v}) boolean OR {u} is also a dominating set of G. The secure domination number gamma(s)(G) is the cardinality of a smallest secure dominating set of G. In this paper, we propose a linear-time algorithm for finding the secure domination number of cographs. (C) 2019 Elsevier B.V. All rights reserved.

关键词： graph algorithm Secure domination Cograph

来源：评论

学校读者我要写书评

暂无评论

Traversal with Enumeration of Geometric graphs in Bounded Space

引用

JOURNAL OF INTERCONNECTION NETWORKS 2019年第4期19卷

作者： Khakabimamaghani, Sahand Masjoody, Masood Stacho, Ladislav Simon Fraser Univ Dept Comp Sci 8888 Univ Dr Burnaby BC V5A 1S6 Canada Simon Fraser Univ Dept Math 8888 Univ Dr Burnaby BC V5A 1S6 Canada

In this paper, we provide an algorithm for traversing geometric graphs which visits all vertices and reports every vertex and edge exactly once. To achieve this, we combine a given geometric graph G with the integer lattice, seen as a graph, in such a way that the resulting hypothetical graph can be traversed using a known algorithm which is based on face routing. To overcome the problem with hypothetical vertices and edges, we develop an algorithm for visiting any k-th neighborhood of a vertex in a graph straight-line drawn in the plane using O(k log k) memory. The memory needed to complete the traversal of a geometric graph then turns out to depend on the maximum graph distance among pairs of distinct vertices of G whose Euclidean distance is greater than one and less than 2 root 2.

关键词： graph algorithm traversal geometric graph quasi-planar subdivision

来源：评论

学校读者我要写书评

暂无评论

Safe sets in graphs: graph classes and structural parameters

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第4期36卷 1221-1242页

作者： Agueda, Raquel Cohen, Nathann Fujita, Shinya Legay, Sylvain Manoussakis, Yannis Matsui, Yasuko Montero, Leandro Naserasr, Reza Ono, Hirotaka Otachi, Yota Sakuma, Tadashi Tuza, Zsolt Xu, Renyu Univ Castilla La Mancha Ciudad Real Spain Univ Paris Sud LRI Orsay France Yokohama City Univ Yokohama Kanagawa Japan Tokai Univ Tokyo Japan Univ Paris Diderot LIAFA Paris France Nagoya Univ Nagoya Aichi Japan Kumamoto Univ Kumamoto Japan Yamagata Univ Yamagata Japan MTA Renyi Inst Budapest Hungary Univ Pannonia Veszprem Hungary Shandong Univ Jinan Shandong Peoples R China

A safe set of a graph is a non-empty subset S of V such that for every component A of G[S] and every component B of , we have whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.

关键词： Safe set graph algorithm graph class Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Efficient Dispersion of Mobile Robots on graphs 19

Efficient Dispersion of Mobile Robots on Graphs

引用

20th International Conference on Distributed Computing and Networking (ICDCN)

作者： Kshemkalyani, Ajay D. Ali, Faizan Univ Illinois Chicago IL 60612 USA

ISBN: (纸本)9781450360944

The dispersion problem on graphs requires k robots placed arbitrarily at the n nodes of an anonymous graph, where k <= n, to coordinate with each other to reach a final configuration in which each robot is at a distinct node of the graph. The dispersion problem is important due to its relationship to graph exploration by mobile robots, scattering on a graph, and load balancing on a graph. In addition, an intrinsic application of dispersion has been shown to be the relocation of self-driven electric cars (robots) to recharge stations (nodes). We propose five algorithms to solve dispersion on graphs. The first three algorithms require O(k log Delta) bits at each robot andO(m) steps running time, wherem is the number of edges and Delta is the degree of the graph. The algorithms differ in whether they address the synchronous or the asynchronous system model, and in what, where, and how data structures are maintained. The fourth algorithm, for the asynchronous model, has a space usage of O(D log Delta) bits at each robot and uses O(Delta(D)) steps, where D is the graph diameter. The fifth algorithm, for the asynchronous model, has a space usage of O(max(log k, log Delta)) bits at each robot and uses O((m - n) k) steps.

关键词： distributed algorithm dispersion graph algorithm graph exploration mobile robot collective robot exploration

来源：评论

学校读者我要写书评

暂无评论

Optimal Partition of a Tree with Social Distance 13th

Optimal Partition of a Tree with Social Distance

引用

13th International Conference on algorithms and Computation (WALCOM)

作者： Okubo, Masahiro Hanaka, Tesshu Ono, Hirotaka Nagoya Univ Grad Sch Informat Chikusa Ku Furo Cho Nagoya Aichi Japan Chuo Univ Dept Informat & Syst Engn Bunkyo Ku 1-13-27 Kasuga Tokyo Japan

ISBN: (纸本)9783030105648;9783030105631

We study the problem to find a partition of a graph G with maximum social welfare based on social distance between vertices in G, called MaxSWP. This problem is known to be NP-hard in general. In this paper, we first give a complete characterization of optimal partitions of trees with small diameters. Then, by utilizing these results, we show that MaxSWP can be solved in linear time for trees. Moreover, we show that MaxSWP is NP-hard even for 4-regular graphs.

关键词： graph algorithm Tree graph partition Social distance

来源：评论

学校读者我要写书评

暂无评论

A survey of graph processing on graphics processing units

引用

JOURNAL OF SUPERCOMPUTING 2018年第5期74卷 2086-2115页

作者： Ha-Nguyen Tran Cambria, Erik Nanyang Technol Univ Sch Comp Sci & Engn Singapore Singapore

graphics processing units (GPUs) have become popular high-performance computing platforms for a wide range of applications. The trend of processing graph structures on modern GPUs has also attracted an increasing interest in recent years. This article aims to review research works on adapting the massively parallel architecture of GPUs to accelerate the performance of fundamental graph operations. Despite their merits, some factors such as the unique architecture of GPUs, limited programming models, and irregular structures of graphs prevent GPU implementations from achieving high performance. Thus, this survey also discusses challenges and optimization techniques used by recent studies to fully utilize the GPU capability. A categorization of the existing research works is also presented based on the specific issues these attempted to solve.

关键词： Introductory and survey graphics processor GPU graph processing graph algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：