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

exact exponential algorithm for Distance-3 Independent Set Problem

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2019年第3期E102D卷 499-501页

作者： Yamanaka, Katsuhisa Kawaragi, Shogo Hirayama, Takashi Iwate Univ Fac Sci & Engn Morioka Iwate 0208551 Japan

Let G = (V, E) be an unweighted simple graph. A distance-d independent set is a subset I subset of V such that dist(u, v) >= d for any two vertices u, v in I, where dist(u, v) is the distance between u and v. Then, Maximum Distance-d Independent Set problem requires to compute the size of a distance-d independent set with the maximum number of vertices. Even for a fixed integer d >= 3, this problem is NP-hard. In this paper, we design an exact exponential algorithm that calculates the size of a maximum distance-3 independent set in O(1.4143(n)) time.

关键词： exact exponential algorithm independent set distance-d independent set maximum distance-d independent set

来源：评论

学校读者我要写书评

暂无评论

An exact exponential branch-and-merge algorithm for the single machine total tardiness problem

引用

THEORETICAL COMPUTER SCIENCE 2018年 745卷 133-149页

作者： Garraffa, Michele Shang, Lei Della Croce, Federico T'kindt, Vincent DAUIN Politecn Torino Turin Italy ERL CNRS 7002 ROOT Lab Informat Fondamentale & Appl EA 6300 Tours France DIGEP Politecn Torino Turin Italy CNR IEIIT Turin Italy

This paper proposes an exact exponential algorithm for the single machine total tardiness problem. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property that solves the problem with worst-case complexity in time O*(3(n)) and polynomial space. The proposed algorithm, called branch and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity converges to O*(2(n)) keeping the space complexity polynomial. This improves upon the best-known complexity result for this problem provided by dynamic programming across the subsets with O*(2(n)) worst-case time and space complexity. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties. (C) 2018 Elsevier B.V. All rights reserved.

关键词： exact exponential algorithm Single machine total tardiness Branch and merge

来源：评论

学校读者我要写书评

暂无评论

On the minimum feedback vertex set problem: exact and enumeration algorithms

引用

algorithmICA 2008年第2期52卷 293-307页

作者： Fomin, Fedor V. Gaspers, Serge Pyatkin, Artem V. Razgon, Igor Univ Bergen Dept Informat N-5020 Bergen Norway SB RAS Sobolev Inst Math Novosibirsk 630090 Russia Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Ireland

We present a time O(1.7548(n)) algorithm finding a minimum feedback vertex set in an undirected graph on n vertices. We also prove that a graph on n vertices can contain at most 1.8638(n) minimal feedback vertex sets ... 详细信息

关键词： minimum feedback vertex set maximum induced forest exact exponential algorithm number of minimal feedback vertex sets

来源：评论

学校读者我要写书评

暂无评论

An Improved exact algorithm for TSP in Graphs of Maximum Degree 4

引用

THEORY OF COMPUTING SYSTEMS 2016年第2期58卷 241-272页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan

The paper presents a 1.692(n)n(O(1))-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890(n)n(O(1))-time polynomial-space algorithm by Eppstein and the 1.733(n)n(O(1))-time exponential-space algorithm by Gebauer.

关键词： Traveling salesman problem exact exponential algorithm Graph algorithm Measure-and-conquer

来源：评论

学校读者我要写书评

暂无评论

On the complexity of computing treelength

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 820-827页

作者： Lokshtanov, Daniel Univ Bergen Dept Informat N-5020 Bergen Norway

We resolve the computational complexity of determining the treelength of a graph, thereby solving an open problem of Dourisboure and Gavoille, who introduced this parameter, and asked to determine the complexity of recognizing graphs of a bounded treelength Dourisboure and Gavoille (2007)[6]. While recognizing graphs with treelength 1 is easily seen as equivalent to recognizing chordal graphs, which can be done in linear time, the computational complexity of recognizing graphs with treelength 2 was unknown until this result. We show that the problem of determining whether a given graph has a treelength at most k is NP-complete for every fixed k >= 2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than (3)/(2).Additionally, we show that treelength can be computed in time O*(1.7549(n)) by giving an exact exponential time algorithm for the Chordal Sandwich problem and showing how this algorithm can be used to compute the treelength of a graph. (c) 2009 Elsevier B.V. All rights reserved.

关键词： Graph treelength NP-complete Approximation Inapproximability exact exponential algorithm Chordal sandwich problem

来源：评论

学校读者我要写书评

暂无评论

On distance-preserving elimination orderings in graphs: Complexity and algorithms

引用

DISCRETE APPLIED MATHEMATICS 2018年 243卷 140-153页

作者： Coudert, David Ducoffe, Guillaume Nisse, Nicolas Soto, Mauricio Univ Cote Azur INRIA CNRS Nice France ICI Natl Inst Res & Dev Informat Bucharest Romania Univ Bucharest ICUB Res Inst Bucharest Romania Univ Chile Dept Ingn Matemat Fac Ciencias Fis & Matemat Santiago Chile

For every connected graph G, a subgraph H of G is isometric if the distance between any two vertices in H is the same in H as in G. A distance-preserving elimination ordering of G is a total ordering of its vertex-set V (G), denoted (v(1), v(2),....v(n)), such that any subgraph G(i)= G \ (v(1), v(2),, v(i)) with 1 <= i < n is isometric. This kind of ordering has been introduced by Chepoi in his study on weakly modular graphs (Chepoi, 1998). We prove that it is NP complete to decide whether such ordering exists for a given graph even if it has diameter at most 2. Then, we prove on the positive side that the problem of computing a distance preserving ordering when there exists one is fixed-parameter-tractable in the treewidth. Lastly, we describe a heuristic in order to compute a distance-preserving ordering when there exists one that we compare to an exact exponential time algorithm and to an ILP formulation for the problem. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Distance-preserving elimination ordering Metric graph theory NP-complete exact exponential algorithm Integer linear programming Bounded treewidth

来源：评论

学校读者我要写书评

暂无评论

An algorithm for Listing all Minimal Double Dominating Sets of a Tree

引用

FUNDAMENTA INFORMATICAE 2014年第4期130卷 415-421页

作者： Krzywkowski, Marcin Gdansk Univ Technol Fac Elect Telecommun & Informat Gdansk Poland Polish Acad Sci Inst Math PL-00901 Warsaw Poland

We provide an algorithm for listing all minimal double dominating sets of a tree of order n in time O(1.3248(n)). This implies that every tree has at most 1.3248(n) minimal double dominating sets. We also show that th... 详细信息

关键词： domination double domination minimal double dominating set tree combinatorial bound exact exponential algorithm listing algorithm

来源：评论

学校读者我要写书评

暂无评论

Structural parameterizations of budgeted graph coloring

引用

THEORETICAL COMPUTER SCIENCE 2023年第PartA期940卷 209-221页

作者： Bandopadhyay, Susobhan Banerjee, Suman Banik, Aritra Raman, Venkatesh Natl Inst Sci Educ & Res Bhubaneswar 752050 Odisha India Indian Inst Technol Dept Comp Sci & Engn Jammu India HBNI Inst Math Sci Chennai India

We introduce a variant of the graph coloring problem, which we denote as BUDGETED COLORING PROBLEM (BCP). Given a graph G, an integer c and an ordered list of integers (b1, b2, ... , bc), BCP asks whether there exists a proper coloring of G where the i-th color is used to color at most bi many vertices. This problem generalizes two well-studied graph coloring problems, BOUNDED COLORING PROBLEM (BOCP) and EQUITABLE COLORING PROBLEM (ECP) and as in the case of other coloring problems, the BCP is NP-hard even for constant values of c. So we study BCP under the paradigm of parameterized complexity, particularly with respect to (structural) parameters that specify how far (the deletion distance) the input graph is from a tractable graph *** dot We show that BCP is FPT (fixed-parameter tractable) parameterized by the vertex cover size. This generalizes a similar result for ECP and immediately extends to the BoCP, which was earlier not *** dot We show that BCP is polynomial time solvable for cluster graphs generalizing a similar result for ECP. However, we show that BCP is FPT, but unlikely to have polynomial kernel, when parameterized by the deletion distance to clique, contrasting the linear kernel for ECP for the same *** dot While the BoCP is known to be polynomial time solvable on split graphs, we show that BCP is NP-hard on split graphs. As BoCP is hard on bipartite graphs when c > 3, the result follows for BCP as well. We provide a dichotomy result by showing that BCP is polynomial time solvable on bipartite graphs when c = 2. We also show that BCP is NP-hard on co-cluster graphs, contrasting the polynomial time algorithm for ECP and *** we present an O*(2|V(G)|) algorithm for the BCP, generalizing the known algorithm with a similar bound for the standard chromatic number.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Graph coloring exact exponential algorithm Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of and solutions to the minimum stopping and trapping set problems

引用

THEORETICAL COMPUTER SCIENCE 2022年 915卷 26-44页

作者： Velasquez, Alvaro Subramani, K. Wojciechowski, Piotr AF Res Lab Informat Directorate Rome NY 13441 USA West Virginia Univ LCSEE Morgantown WV 26506 USA

In this paper, we discuss the problems of finding minimum stopping sets and trapping sets in Tanner graphs, using integer linear programming. These problems are important for establishing reliable communication across noisy channels. Indeed, stopping sets and trapping sets correspond to combinatorial structures in information-theoretic codes, which lead to errors in decoding once a message is received. In particular, these sets correspond to variables that are not eventually corrected by the decoder, thus causing failures in decoding when using iterative algorithms. We present integer linear programs (ILPs) for finding stopping sets and several trapping set variants. Furthermore, we prove that two of these trapping set problem variants are NP-hard for the first time. Additionally, we analyze these variants from the parameterized perspective. Finally, we model stopping set and trapping set problems as Integer Linear Programs (ILPs). The effectiveness of our approach is demonstrated by finding stopping sets of size up to 48 in the (4896, 2474) Margulis code. This compares favorably to the current state-of-the-art, which finds stopping sets of size up to 26. For the trapping set problems, we show for which cases an ILP produces solutions efficiently and for which cases it performs poorly. The proposed approach is applicable to codes represented by regular and irregular graphs alike.(1) (c) 2022 Elsevier B.V. All rights reserved.

关键词： Stopping set Trapping set NP-complete Parameterized algorithm exact exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for treewidth and minimum fill-in

引用

SIAM JOURNAL ON COMPUTING 2008年第3期38卷 1058-1079页

作者： Fomin, Fedor V. Kratsch, Dieter Todinca, Ioan Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway Univ Metz LITA F-57045 Metz 01 France Univ Orleans LIFO F-45067 Orleans 2 France

We show that the treewidth and the minimum fill-in of an n-vertex graph can be computed in time O(1.8899(n)). Our results are based on combinatorial proofs that an n-vertex graph has O(1.7087(n)) minimal separators and O(1.8135(n)) potential maximal cliques. We also show that for the class of asteroidal triple-free graphs the running time of our algorithms can be reduced to O(1.4142(n)).

关键词： exact exponential algorithm treewidth fill-in minimal separators potential maximal clique minimal triangulation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：