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

The perfect matching cut problem revisited

THEORETICAL COMPUTER SCIENCE 2022年 931卷 117-130页

作者： Le, Van Bang Telle, Jan Arne Univ Rostock Inst Informat Rostock Germany Univ Bergen Dept Informat N-5020 Bergen Norway

In a graph, a perfect matching cut is an edge cut that is a perfect matching. PERFECT MATCHING CUT (PMC) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be NP-complete. We revisit the problem and show that PMC remains NP-complete when restricted to bipartite graphs of maximum degree 3 and arbitrarily large girth. Complementing this hardness result, we give two graph classes in which PMC is polynomial-time solvable. The first one includes claw-free graphs and graphs without an induced path on five vertices, the second one properly contains all chordal graphs. Assuming the Exponential Time Hypothesis, we show there is no O*(2o(n))-time algorithm for PMC even when restricted to n-vertex bipartite graphs, and also show that PMC can be solved in O*(1.2721n) time by means of an exact branching algorithm.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Matching cut Perfect matching cut Computational complexity Exact branching algorithm graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithm for Finding Representation of Subtree Distance

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2022年第8期E105卷 1203-1210页

作者： Maehara, Takanori Ando, Kazutoshi RIKEN Ctr Adv Intelligence Project Discrete Optimizat Unit Tokyo Japan Shizuoka Univ Dept Math & Syst Engn Shizuoka Japan

In this paper, we address the problem of finding a representation of a subtree distance, which is an extension of a tree metric. We show that a minimal representation is uniquely determined by a given subtree distance, and give an O(n(2)) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Omega(n(2)), our algorithm achieves the optimal time complexity.

关键词： graph algorithm phylogenetic tree tree metric subtree distance

来源：评论

学校读者我要写书评

暂无评论

The Shortest Path Reconfiguration Problem Based on Relaxation of Reconfiguration Rules 1

引用

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Domon, Naoki Suzuki, Akira Tamura, Yuma Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi Japan

ISBN: (数字)9789819705665

ISBN: (纸本)9789819705658;9789819705665

The shortest path problem is the most classical and fundamental problem in the field of graph algorithm. Recently, its reconfiguration variant, namely the Shortest Path Reconfiguration problem, has received a lot of attention. In this paper, we study the complexity of k-SPR, which generalizes the Shortest Path Reconfiguration problem, with respect to k. In k-SPR, we are allowed to replace at most k consecutive vertices of the current shortest path at a time. We first show that, for any fixed rational numbers c and epsilon such that c > 0 and 0 < epsilon <= 1, k-SPR with k = cn(1-epsilon) is polynomially solvable if epsilon = 1 and c < 1;otherwise, PSPACE-complete. This intractability holds even when given graphs are restricted to bipartite graphs and r-th power graphs, where r is any positive integer. Furthermore, when we restrict 0 < epsilon < 1, the PSPACE-completeness holds for graphs with maximum degree 3. Then, we design an FPT algorithm parameterized by mu = n/2 - k >= 0 that runs in O(m + 6.730(mu) mu(4) n) time. Finally, we show that, for any k, k-SPR can be solved in linear time for K-2,K-3-minor-free graphs.

关键词： Reconfiguration problem graph algorithm Parameterized complexity Shortest path

来源：评论

学校读者我要写书评

暂无评论

Extension of Parallel Primitives and Their Applications to Large-Scale Data Processing 35th

Extension of Parallel Primitives and Their Applications to L...

引用

35th International Conference on Database and Expert Systems Applications (DEXA)

作者： Nakano, Masashi Chang, Qiong Miyazaki, Jun Tokyo Inst Technol Sch Comp Dept Comp Sci Tokyo Japan

ISBN: (纸本)9783031683114;9783031683121

Data parallel primitives are highly optimized general-purpose algorithms designed only for GPUs and are used as building blocks to develop applications. However, existing data parallel primitives cannot handle data larger than the GPU memory size. In this paper, we propose an extension to existing data parallel primitives to efficiently handle data larger than the GPU memory size by cooperatively using both GPUs and CPUs. Moreover, we evaluate the impact of these primitives when applying them to large data processing applications, with respect to both performance and software development cost.

关键词： GPU Data parallel primitives Database processing graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Shortest Two Disjoint Paths in Conservative graphs 41

Shortest Two Disjoint Paths in Conservative Graphs

引用

41st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Schlotter, Ildiko Ctr Econ & Reg Studies Budapest Hungary Budapest Univ Technol & Econ Budapest Hungary

ISBN: (纸本)9783959773119

We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = ( V, E) with edge weights w : E -> R, two terminals s and t in G, find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebo (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the SHORTEST TWO DISJOINT PATHS problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G.

关键词： Shortest paths disjoint paths conservative weights graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Ontology Reshaping for Knowledge graph Construction: Applied on Bosch Welding Case 21st

Ontology Reshaping for Knowledge Graph Construction: Applied...

引用

21st International Semantic Web Conference (ISWC)

作者： Zhou, Dongzhuoran Zhou, Baifan Zheng, Zhuoxun Soylu, Ahmet Cheng, Gong Jimenez-Ruiz, Ernesto Kostylev, Egor V. Kharlamov, Evgeny Bosch Ctr Artificial Intelligence Renningen Germany Univ Oslo Dept Informat Oslo Norway Oslo Metropolitan Univ Dept Comp Sci Oslo Norway Nanjing Univ State Key Lab Novel Software Technol Nanjing Peoples R China City Univ London Dept Comp Sci London England

ISBN: (纸本)9783031194320;9783031194337

Automatic knowledge graph (KG) construction is widely used in industry for data integration and access, and there are several approaches to enable (semi-)automatic construction of knowledge graphs. One important approach is to map the raw data to a given knowledge graph schema, often a domain ontology, and construct the entities and properties according to the ontology. However, the existing approaches to construct knowledge graphs are not always efficient enough and the resulting knowledge graphs are not sufficiently application-oriented and user-friendly. The challenge arises from the trade-off: the domain ontology should be knowledge-oriented, to reflect the general domain knowledge rather than data particularities;while a knowledge graph schema should be data-oriented, to cover all data features. If the former is directly used as the knowledge graph schema, this can cause issues like blank nodes created due to classes unmapped to data and deep knowledge graph structures. To this end, we propose a system for ontology reshaping, which generates knowledge graph schemata that fully cover the data while also covers domain knowledge well. We evaluated our approach extensively with a user study and three real manufacturing datasets from Bosch against four baselines, showing promising results.

关键词： Semantic data integration Knowledge graph Ontology reshaping graph algorithm Automatic knowledge graph construction

来源：评论

学校读者我要写书评

暂无评论

Improved approximation for maximum edge colouring problem

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 42-52页

作者： Chandran, L. Sunil Lahiri, Abhiruk Singh, Nitin Indian Inst Sci Dept Comp Sci & Automat Bangalore India IBM India Res Lab Bangalore India

The anti-Ramsey number, ar(G, H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H, namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erdos and Simonovits in 1973. Since then the parameter has been studied extensively. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q-colouring problem: Find a colouring of the edges of G, maximizing the number of colours satisfying the constraint that each vertex spans at most q colours on its incident edges. It is easy to see that the maximum value of the above optimization problem equals ar(G, K1,q+1) - 1. In this paper, we study the maximum edge 2-colouring problem from the approx-imation algorithm point of view. The case q = 2 is particularly interesting due to its application in real-life problems. algorithmically, this problem is known to be NP-hard for q - 2. For the case of q = 2, it is also known that no polynomial-time algorithm can approximate to a factor less than 3/2 assuming the unique games conjecture. Feng et al. showed a 2-approximation algorithm for this problem. Later Adamaszek and Popa presented a 5/3-approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say M) and different colours to the connected components of G \ M. In this article, we give a new analysis of the aforementioned algorithm to show that for triangle-free graphs with perfect matching the approximation ratio is 8/5. We also show that this algorithm cannot achieve a factor better than 58/37 o

关键词： Approximation algorithm graph algorithm graph colouring Anti-Ramsey number

来源：评论

学校读者我要写书评

暂无评论

On the decomposition of circulant graphs using algorithmic approaches

引用

ALEXANDRIA ENGINEERING JOURNAL 2022年第10期61卷 8263-8275页

作者： El-Mesady, A. Hamed, Y. S. Shabana, H. Menoufia Univ Fac Elect Engn Dept Phys & Engn Math Menoufia 32952 Egypt Taif Univ Coll Sci Dept Math & Stat POB 11099 Taif 21944 Saudi Arabia

Many structural models in chemistry, biology, computer science, sociology, and operations research can be analyzed using graph theory. Some examples of these structure models are species movement between regions, molecular bonds, shortest spanning trees, development of computer algorithms. This paper introduces the edge decomposition of circulant graphs with 2n vertices by different graph classes. These circulant graphs are denoted as C-2n,C-n, where n is the degree of the graph C-2n,C-n. We propose two algorithmic approaches for constructing edge decomposition of C-2n,C-n. With aid of the proposed algorithmic approaches, we construct paths decompositions, trees decompositions, disjoint unions of cycles and trees decompositions, and complete bipartite graphs decompositions of C-2n,C-n. In the end, a recursive construction of an edge decomposition, based on orthogonal edge decompositions, is proposed. This helps in using the mutually orthogonal decompositions of the circulant graphs C2n,n in several applications, such as the design of experiments and binary codes generation. (C) 2022 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Engineering, Alexandria University.

关键词： Circulant graph Decomposition graph translation graph algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Connected Feedback Vertex Set on AT-Free graphs 34th

Connected Feedback Vertex Set on AT-Free Graphs

引用

34th International Workshop on Combinatorial algorithms (IWOCA)

作者： Mukherjee, Joydeep Saha, Tamojit Ramakrishna Mission Vivekananda Educ & Res Inst Howrah India TCG CREST Inst Adv Intelligence Kolkata India

ISBN: (纸本)9783031343469;9783031343476

A connected feedback vertex set of a graph is a connected subgraph of the graph whose removal makes the graph cycle free. In this paper, we give an approximation algorithm that computes a connected feedback vertex set of size (1.9091OPT + 6) on 2-connected AT-free graphs with running time O(n(8)m(2)). Also, we give another approximation algorithm that computes a connected feedback vertex set of size (2.9091OPT + 6) on the same graph class with more efficient running time O(min{m(log(n)), n(2)}).

关键词： graph algorithm Approximation algorithm AT-free graph Feedback Vertex Set Combinatorial Optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：