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

Parameterized complexity of independent set reconfiguration problems

DISCRETE APPLIED MATHEMATICS 2020年 283卷 336-345页

作者： Ito, Takehiro Kaminski, Marcin Ono, Hirotaka Suzuki, Akira Uehara, Ryuhei Yamanaka, Katsuhisa Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan Univ Warsaw Dept Math Comp Sci & Mech Banacha 2 PL-02097 Warsaw Poland Nagoya Univ Grad Sch Informat Chikusa Ku Furocho Nagoya Aichi 4648601 Japan JAIST Sch Informat Sci Asahidai 1-1 Nomi Ishikawa 9231292 Japan Iwate Univ Fac Sci & Engn Ueda 4-3-5 Morioka Iwate 0208551 Japan

Suppose that we are given two independent sets I-0 and I-r of a graph such that vertical bar I-0 vertical bar = vertical bar I-r vertical bar, and imagine that a token is placed on each vertex in I-0. Then, the token jumping problem is to determine whether there exists a sequence of independent sets which transforms I-0 into I-r so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is PSPACE-complete even for planar graphs with maximum degree three. In this paper, we first show that the problem is W[1]-hard when parameterized only by the number of tokens. We then give an FPT algorithm for general graphs when parameterized by both the number of tokens and the maximum degree. Our FPT algorithm can be modified so that it finds an actual sequence of independent sets between I-0 and I-r with the minimum number of token movements. We finally show that one of the results for token jumping can be extended to a more generalized reconfiguration problem for independent sets, called TOKEN ADDITION AND REMOVAL. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration Fixed parameter tractability graph algorithm Independent set

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A hybrid method for solving multi-depot VRP with simultaneous pickup and delivery incorporated with Weber basis saving heuristic

引用

JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING 2016年第1期10卷

作者： Shimizu, Yoshiaki Sakaguchi, Tatsuhiko Yoo, Jae-Kyu Toyohashi Univ Technol Dept Mech Engn 1-1 HibarigaokaTenpaku Cho Toyohashi Aichi 4418580 Japan Kanazawa Univ Sch Econ Kakuma Cho Kanazawa Ishikawa 9201192 Japan

Under growing concerns with sustainability in global and changing market, establishing a cooperative and competitive logistic is becoming a keen issue to provide manufacturing systems amenable to sales and operations planning. As a deployment for such practice, we have engaged in the various studies on logistics optimization. Especially, noticing that transportation cost and/or CO2 emission actually depend not only on distance but also loading weight (Weber basis), we have recently developed a few hybrid meta-heuristic methods for vehicle routing problems (VRP) and shown their effectiveness through numerical experiments. To the best of our knowledge, however, there exist no studies that take the Weber basis into account on VRP except for ours. As a hot interest in this area, we pay our attention on VRP with simultaneous pickup and delivery (VRPSPD). Then, this study attempts to extend the foregoing Weber basis study under single depot to multi-depot problem and intends to reveal some properties of VRPSPD. To work with such concerns, we have developed a novel hierarchical method comprised of a modified tabu search, a graph algorithm for the minimum cost flow problem and a Weber basis saving method. The proposed method is possible to solve various real world applications practically even with large problem sizes. Finally, the effectiveness of the proposed method is validated through numerical experiments taken place from various viewpoints to discuss about some peculiar features of VRPSPD.

关键词： Multi-depot VRPSPD Hybrid approach Weber basis saving method graph algorithm Modified tabu search

来源：评论

学校读者我要写书评

暂无评论

EvoArch: An evolutionary algorithm for architectural layout design

引用

COMPUTER-AIDED DESIGN 2009年第9期41卷 649-667页

作者： Wong, Samuel S. Y. Chan, Keith C. C. Hong Kong Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China

The architectural layout design problem, which is concerned with the finding of the best adjacencies between functional spaces among many possible ones under given constraints, can be formulated as a combinatorial optimization problem and can be solved with an Evolutionary algorithm (EA). We present functional spaces and their adjacencies in form of graphs and propose an EA called EvoArch that works with a graph-encoding scheme. EvoArch encodes topological configuration in the adjacency matrices of the graphs that they represent and its reproduction operators operate on these adjacency matrices. In order to explore the large search space of graph topologies, these reproduction operators are designed to be unbiased so that all nodes in a graph have equal chances of being selected to be swapped or mutated. To evaluate the fitness of a graph, EvoArch makes use of a fitness function that takes into consideration preferences for adjacencies between different functional spaces, budget and other design constraints. By means of different experiments, we show that EvoArch can be a very useful tool for architectural layout design tasks. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Architectural space topology Evolutionary algorithm Crossover Genetic algorithm graph algorithm Mutation

来源：评论

学校读者我要写书评

暂无评论

algorithmic aspects of clique-transversal and clique-independent sets

引用

DISCRETE APPLIED MATHEMATICS 2000年第3期100卷 183-202页

作者： Guruswami, V Rangan, CP Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India

A minimum clique-transversal set MCT(G) of a graph G = (V,E) is a set S subset of or equal to V of minimum cardinality that meets all maximal cliques in G. A maximum clique-independent set MCI(G) of G is a set of maximum number of pairwise vertex-disjoint maximal cliques. We prove that the problem of finding an MCT(G) and an MCI(G) is NP-hard for cocompatability, planar, line and total graphs. As an interesting corollary we obtain that the problem of finding a minimum number of elements of a poset to meet all maximal antichains of the poset remains NP-hard even if the poset has height two, thereby generalizing a result of Duffas et al. (J. Combin. Theory Ser. A 58 (1991) 158-164). We present a polynomial algorithm for the above problems on Helly circular-are graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms for the weighted version of the clique-transversal problem on strongly chordal graphs, chordal graphs of bounded clique size, and cographs. The algorithms presented run in linear time for strongly chordal graphs and cographs. These mark the first attempts at the weighted version of the problem. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： graph algorithm NP-hardness clique-transversal set clique-independent set line graph total graph poset

来源：评论

学校读者我要写书评

暂无评论

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 efficient algorithm for distance total domination in block graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期31卷 372-381页

作者： Zhao, Yancai Shan, Erfang Wuxi City Coll Vocat Technol Dept Basic Sci Wuxi 214153 Jiangsu Peoples R China Shanghai Univ Sch Management Shanghai 200444 Peoples R China

The -distance total domination problem is to find a minimum vertex set of a graph such that every vertex of the graph is within distance from some vertex of other than itself, where is a fixed positive integer. In the present paper, by using a labeling method, we design an efficient algorithm for solving the -distance total domination problem on block graphs, a superclass of trees.

关键词： graph algorithm Total domination k-Distance total domination Block graph

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：