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

22nd International Computing and Combinatorics Conference (COCOON)

作者： Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

ISBN: (纸本)9783319426341;9783319426334

The d-bounded-degree vertex deletion problem, to delete at most k vertices in a given graph to make the maximum degree of the remaining graph at most d, finds applications in computational biology, social network analysis and some others. It can be regarded as a special case of the (d + 2)-hitting set problem and generates the famous vertex cover problem. The d-bounded-degree vertex deletion problem is NP-hard for each fixed d >= 0. In terms of parameterized complexity, the problem parameterized by k is W[2]-hard for unbounded d and fixed-parameter tractable for each fixed d >= 0. Previously, (randomized) parameterized algorithms for this problem with running time bound O*((d + 1)(k)) are only known for d <= 2. In this paper, we give a uniform parameterized algorithm deterministically solving this problem in O*((d + 1)(k)) time for each d >= 3. Note that it is an open problem whether the d ' -hitting set problem can be solved in O*((d ' - 1)(k)) time for d ' >= 3. Our result answers this challenging open problem affirmatively for a special case. Furthermore, our algorithm also gets a running time bound of O*(3.0645(k)) for the case that d = 2, improving the previous deterministic bound of O*(3.24(k)).

关键词： parameterized algorithms Graph algorithms Bounded-degree vertex deletion Hitting set

来源：评论

学校读者我要写书评

暂无评论

Paths of Bounded Length and Their Cuts: parameterized Complexity and Algorithm

Paths of Bounded Length and Their Cuts: Parameterized Comple...

引用

4th International Workshop on parameterized and Exact Computation

作者： Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Athens Dept Math Natl & Kapodistrian GR-15784 Athens Greece

ISBN: (纸本)9783642112683

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem anti the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target;paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both A: and I and hardness results when the parameter is only one of A: and I. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.

关键词： Bounded length disjoint paths Bounded length cuts parameterized Complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

P- Matchings parameterized by Treewidth 49th

P- Matchings Parameterized by Treewidth

引用

49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Chaudhary, Juhi Zehavi, Meirav Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9783031433795;9783031433801

A matching is a subset of edges in a graph G that do not share an endpoint. A matching M is a P-matching if the subgraph of G induced by the endpoints of the edges of M satisfies property P. For example, if the property P is that of being a matching, being acyclic, or being disconnected, then we obtain an induced matching, an acyclic matching, and a disconnected matching, respectively. In this paper, we analyze the problems of the computation of these matchings from the viewpoint of parameterized Complexity with respect to the parameter treewidth.

关键词： Matching Treewidth parameterized algorithms Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

Efficient computation of the oriented chromatic number of recursively defined digraphs

引用

INTERNATIONAL JOURNAL OF CARDIOLOGY 2021年 343卷 16-35页

作者： Gurski, Frank Komander, Dominique Lindemann, Marvin Heinrich Heine Univ Inst Comp Sci Algorithm Hard Problems Grp D-40225 Dusseldorf Germany

In this paper we consider colorings of oriented graphs, i.e. digraphs without cycles of length 2. Given some oriented graph G = (V, E), an oriented r-coloring for G is a partition of the vertex set V into r independent sets, such that all the arcs between two of these sets have the same direction. The oriented chromatic number of G is the smallest integer r such that G permits an oriented r-coloring. Deciding whether an acyclic digraph has an oriented 4-coloring is NP-hard, which motivates to consider the problem on special graph classes. In this paper we consider the Oriented Chromatic Number problem on classes of recursively defined oriented graphs. Oriented co-graphs (short for oriented complement reducible graphs) can be recursively defined from the single vertex graph by applying the disjoint union and order composition. This recursive structure allows to compute an optimal oriented coloring and the oriented chromatic number in linear time. We generalize this result using the concept of perfect orderable graphs. Therefore, we show that for acyclic transitive digraphs every greedy coloring along a topological ordering leads to an optimal oriented coloring. Msp-digraphs (short for minimal series-parallel digraphs) can be defined from the single vertex graph by applying the parallel composition and series composition. We prove an upper bound of 7 for the oriented chromatic number for msp-digraphs and we give an example to show that this is bound best possible. We apply this bound and the recursive structure of msp-digraphs to obtain a linear time solution for computing the oriented chromatic number of msp-digraphs. In order to generalize the results on computing the oriented chromatic number of special graph classes, we consider the parameterized complexity of the Oriented Chromatic Number problem by so-called structural parameters, which are measuring the difficulty of decomposing a graph into a special tree-structure. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Oriented graphs Msp-digraphs Oriented co-graphs Oriented coloring Efficient algorithms Directed clique-width parameterized algorithms CLIQUE-WIDTH GRAPHS COLORINGS PLANAR RECOGNITION COMPLEXITY BOUNDS

来源：评论

学校读者我要写书评

暂无评论

Packing Arc-Disjoint Cycles in Tournaments

引用

ALGORITHMICA 2021年第5期83卷 1393-1420页

作者： Bessy, Stephane Bougeret, Marin Krithika, R. Sahu, Abhishek Saurabh, Saket Thiebaut, Jocelyn Zehavi, Meirav Univ Montpellier CNRS LIRMM Montpellier France Indian Inst Technol Palakkad Palakkad India HBNI Inst Math Sci Chennai Tamil Nadu India Ben Gurion Univ Negev Beer Sheva Israel

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc- disjoint Cycles in Tournaments (ACT.) and Arc- disjoint Triangles in Tournaments (ATT.), respectively. Although the maximization version of ACT. can be seen as the dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT.. We first show that ACT. and ATT. are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT. is fixed-parameter tractable via a 2(O(k log k))n(O(1))-time algorithm and admits a kernel with O(k) vertices. Then, we show that ATT. too has a kernel with O(k) vertices and can be solved in 2(O(k))n(O(1)) time. Afterwards, we describe polynomial-time algorithms for ACT. and ATT. when the input tournament has a feedback arc set that is a matching. We also prove that ACT. and ATT. cannot be solved in 2(o(root n)) n(O(1)) time under the exponential-time hypothesis.

关键词： Arc-Disjoint Cycle Packing Tournaments parameterized algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

An Improved FPT Algorithm for Independent Feedback Vertex Set

引用

THEORY OF COMPUTING SYSTEMS 2020年第8期64卷 1317-1330页

作者： Li, Shaohua Pilipczuk, Marcin Univ Warsaw Inst Informat Warsaw Poland

We study the INDEPENDENT FEEDBACK VERTEX SET problem - a variant of the classic FEEDBACK VERTEX SET problem where, given a graph G and an integer k, the problem is to decide whether there exists a vertex set S. V (G) such that G \ S is a forest and S is an independent set of size at most k. We present an O* ((1+.2)k)time FPT algorithm for this problem, where phi < 1.619 is the golden ratio, improving the previous fastest O* (4.1481k)-time algorithm given by Agrawal et al. (2016). The exponential factor in our time complexity bound matches the fastest deterministic FPT algorithm for the classic FEEDBACK VERTEX SET problem. On the technical side, the main novelty is a refined measure of an input instance in a branching process, that allows for a simpler and more concise description and analysis of the algorithm.

关键词： Independent feedback vertex set parameterized algorithms Branching

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems

引用

COMPUTER JOURNAL 2008年第3期51卷 303-325页

作者： Gottlob, Georg Szeider, Stefan Univ Durham Sci Labs Dept Comp Sci Durham DH1 3LE England Univ Oxford Comp Lab Oxford OX1 3QD England

We survey the parameterized complexity of problems that arise in artificial intelligence, database theory and automated reasoning. In particular, we consider various parameterizations of the constraint satisfaction problem, the evaluation problem of Boolean conjunctive database queries and the propositional satisfiability problem. Furthermore, we survey parameterized algorithms for problems arising in the context of the stable model semantics of logic programs, for a number of other problems of non-monotonic reasoning, and for the computation of cores in data exchange.

关键词： artificial intelligence constraint satisfaction parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Multiple hypernode hitting sets and smallest two-cores with targets

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2009年第3期18卷 294-306页

作者： Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden

The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that, for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic programming algorithm for hypergraphs. The algorithm might be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected.

关键词： Hitting set Job assignment parameterized algorithms Dynamic programming on subsets Cores in graphs

来源：评论

学校读者我要写书评

暂无评论

New and improved algorithms for unordered tree inclusion

引用

THEORETICAL COMPUTER SCIENCE 2021年 883卷 83-98页

作者： Akutsu, Tatsuya Jansson, Jesper Li, Ruiming Takasu, Atsuhiro Tamura, Takeyuki Kyoto Univ Bioinformat Ctr Inst Chem Res Uji Kyoto 6110011 Japan Hong Kong Polytech Univ Dept Comp Hung Hom Kowloon Hong Kong Peoples R China Kyoto Univ Grad Sch Informat Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

The tree inclusion problem is, given two node-labeled trees P and T (the "pattern tree" and the "target tree"), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is a classic algorithm by Kilpelainen and Mannila from 1995 that runs in O (d2(2d)mn) time, where m and n are the sizes of the pattern and target trees, respectively, and d is the degree of the pattern tree. Here, we develop a new algorithm that runs in O (d2(d)mn(2)) time, improving the exponential factor from 2(2d) to 2(d) by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Tree inclusion Unordered trees parameterized algorithms Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Using nondeterminism to design efficient deterministic algorithms

引用

ALGORITHMICA 2004年第2期40卷 83-97页

作者： Chen, JN Friesen, DK Jia, WJ Kanj, IA Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA City Univ Hong Kong Dept Comp Engn & Informat Technol Kowloon Hong Kong Peoples R China DePaul Univ Sch CTI Chicago IL 60604 USA

In this paper we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives a parameterized algorithm of running time O((5.7 k)(k) n) for the 3-D matching problem, which significantly improves the previous algorithm by Downey et al. The algorithm can be generalized to yield an improved algorithm for the r-D matching problem for any positive integer r. The method can also be employed in designing deterministic algorithms for other optimization problems as well.

关键词： three-dimensional matching parameterized algorithms nondeterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：