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

ON GRAPHS COVERABLE BY k SHORTEST PATHS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第2期38卷 1840-1862页

作者： Dumas, Mael Foucaud, Florent Perez, Anthony Todinca, Ioan Univ Orleans INSA Ctr Val de Loire LIFO EA 4022 F-45067 Bourges 2 France Univ Clermont Auvergne CNRS Mines St Etienne LIMOSClermont Auvergne INP F-63000 Clermont Ferrand France

We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a single-exponential function of k. As a corollary, we prove that the problem ISOMETRIC PATH COVER WITH TERMINALS (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem STRONG GEODETIC SET WITH TERMINALS (which, given a graph G and a set of k terminals, asks whether there exist \bigl( k \bigr) shortest paths covering G, each joining a distinct pair of terminals). Moreover, this implies that the related problems ISOMETRIC PATH COVER and STRONG GEODETIC SET (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k.

关键词： covering problems shortest paths graph theory parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Constraint bipartite vertex cover: simpler exact algorithms and implementations

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第3期23卷 331-355页

作者： Bai, Guoqiang Fernau, Henning Univ Trier FB IV Abt Informat D-54286 Trier Germany

Constraint bipartite vertex cover is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations. We also discuss possible generalizations and enhancements.

关键词： Spare allocation problem Constraint bipartite vertex cover parameterized algorithms Implementation and tests of exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity of Secure Sets

引用

ALGORITHMICA 2018年第10期80卷 2909-2940页

作者： Bliem, Bernhard Woltran, Stefan TU Wien Inst Informat Syst 184 2 Favoritenstr 9-11 A-1040 Vienna Austria

A secure set S in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph G and integer k, a non-empty secure set for G of size at most k exists. In this work, we pinpoint the complexity of this problem by showing that it is -complete. Furthermore, the problem has so far not been subject to a parameterized complexity analysis that considers structural parameters. In the present work, we prove that the problem is -hard when parameterized by treewidth. This is surprising since the problem is known to be FPT when parameterized by solution size and "subset problems" that satisfy this property usually tend to be FPT for bounded treewidth as well. Finally, we give an upper bound by showing membership in , and we provide a positive result in the form of an FPT algorithm for checking whether a given set is secure on graphs of bounded treewidth.

关键词： Secure set Complexity analysis parameterized complexity Treewidth parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Courcelle's theorem-A game-theoretic approach

引用

DISCRETE OPTIMIZATION 2011年第4期8卷 568-594页

作者： Kneis, Joachim Langer, Alexander Rossmanith, Peter Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany

Courcelle's theorem states that every problem definable in Monadic Second-Order logic can be solved in linear time on structures of bounded treewidth, for example, by constructing a tree automaton that recognizes or rejects a tree decomposition of the structure. Existing, optimized software like the MONA tool can be used to build the corresponding tree automata, which for bounded treewidth are of constant size. Unfortunately, the constants involved can become extremely large-every quantifier alternation requires a power set construction for the automaton. Here, the required space can become a problem in practical applications. In this paper, we present a novel, direct approach based on model checking games, which avoids the expensive power set construction. Experiments with an implementation are promising, and we can solve problems on graphs where the automata-theoretic approach fails in practice. (C) 2011 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Model checking Monadic Second-Order logic Treewidth

来源：评论

学校读者我要写书评

暂无评论

Derivation of algorithms for cutwidth and related graph layout parameters

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2009年第4期75卷 231-244页

作者： Bodlaender, Hans L. Fellows, Michael R. Thilikos, Dimitrios M. Univ Athens Dept Math GR-15784 Athens Greece Univ Newcastle Off DVC Res Callaghan NSW 2308 Australia Univ Utrecht Inst Comp & Informat Sci NL-3508 TB Utrecht Netherlands

In this paper, we investigate algorithms for some related graph parameters. Each of these asks for a linear ordering of the vertices of the graph (or can be formulated as such), and constructive linear time algorithms for the fixed parameter versions of the problems have been published for several of these. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present ideas in these algorithms in a different more easily accessible manner. by showing that the algorithms can be obtained by a stepwise modification of a trivial hypothetical non-deterministic algorithm. The methodology is applied to rederive known results for the cutwidth and the pathwidth problem, and obtain new results for several variants of these problems, like directed and weighted variants of cutwidth and modified cutwidth. (C) 2008 Elsevier Inc. All rights reserved.

关键词： parameterized algorithms Layout parameters Cutwidth Pathwidth Modified cutwidth Finite state automata

来源：评论

学校读者我要写书评

暂无评论

Seeing the trees and their branches in the network is hard

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期401卷 153-164页

作者： Kanj, Iyad A. Nakhleh, Luay Than, Cuong Xia, Ge Depaul Univ Sch Comp Sci Telecommun & Informat Syst Chicago IL 60604 USA Rice Univ Dept Comp Sci Houston TX 77005 USA Lafayette Coll Acopian Engn Ctr Dept Comp Sci Easton PA 18042 USA

Phylogenetic networks are a restricted class of directed acyclic graphs that model evolutionary histories in the presence of reticulate evolutionary events, such as horizontal gene transfer, hybrid speciation, and recombination. Characterizing a phylogenetic network as a collection of trees and their branches has long been the basis for several methods of reconstructing and evaluating phylogenetic networks. Further, these characterizations have been used to understand molecular sequence evolution on phylogenetic networks. In this paper, we address theoretical questions with regard to phylogenetic networks, their characterizations, and sequence evolution on them. In particular, we prove that the problem of deciding whether a given tree is contained inside a network is NP-complete. Further, we prove that the problem of deciding whether a branch of a given tree is also a branch of a given network is polynomially equivalent to that of deciding whether the evolution of a molecular character (site) on a network is governed by the infinite site model. Exploiting this equivalence, we establish the NP-completeness of both problems, and provide a parameterized algorithm that runs in time O(2(k/2)n(2)), where n is the total number of nodes and k is the number of recombination nodes in the network, which significantly improves upon the trivial brute-force O(2(k)n) time algorithm for the problem. This reduction in time is significant, particularly when analyzing recombination hotspots. (c) 2008 Elsevier B.V. All rights reserved.

关键词： phylogenies networks complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Clustering with partial information

引用

THEORETICAL COMPUTER SCIENCE 2010年第7-9期411卷 1202-1211页

作者： Bodlaender, Hans L. Fellows, Michael R. Heggernes, Pinar Mancini, Federico Papadopoulos, Charis Rosamond, Frances Univ Bergen Dept Informat N-5020 Bergen Norway Univ Newcastle Off DVC Res PCRU Callaghan NSW 2308 Australia Univ Utrecht Dept Informat & Comp Sci NL-3508 TC Utrecht Netherlands

The CORRELATION CLUSTERING problem, also known as the CLUSTER EDITING problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The EDGE CLIQUE PARTITIONING problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided. For fuzzy graphs the CORRELATION CLUSTERING and EDGE CLIQUE PARTITIONING problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the CORRELATION CLUSTERING problem is fixed-parameter tractable on fuzzy graphs when parameterized by (k, r), where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O(k(2) + r) vertices. We provide an analogous result for the EDGE CLIQUE PARTITIONING problem on fuzzy graphs. Using (k, r) as parameters, where k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O(k(4).3(r)) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques k, is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k > 2. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Graphs parameterized algorithms Cluster editing Kernels

来源：评论

学校读者我要写书评

暂无评论

HITTING SELECTED (ODD) CYCLES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2017年第3期31卷 1581-1615页

作者： Lokshtanov, Daniel Misra, Pranabendu Ramanujan, M. S. Saurabh, Saket Univ Bergen Bergen Norway HBNI Inst Math Sci Madras Tamil Nadu India TU Wien Algorithms & Complex Grp Vienna Austria

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph G, a subset of vertices T and a positive integer k and the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle containing a vertex from T. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [Proceedings of SODA, 2012, pp. 1726-1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time f(k)mn(3) using the theory of graph minors, where f is some function, and n and m denote the number of vertices and edges in the graph. However, the dependence of this function on k is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on k is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time 2(O(k3) (log k))mn(2)log(2) n, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of generalized important separators to reduce the subset version of this problem to the standard version of the problem.

关键词： important separators sequence odd cycle transversal graph separation problems parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

New FPT algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees

引用

ALGORITHMICA 2022年第7期84卷 2050-2087页

作者： Borst, Sander van Iersel, Leo Jones, Mark Kelk, Steven Ctr Wiskunde & Informat CWI POB 94079 NL-1090 GB Amsterdam Netherlands Delft Univ Technol Delft Inst Appl Math Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands Maastricht Univ Dept Data Sci & Knowledge Engn DKE POB 616 NL-6200 MD Maastricht Netherlands

We study the problem of finding a temporal hybridization network containing at most k reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m binary trees with n leaves each with a running time of O(5(k).n.m). We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most d and at most k reticulations in O((8k)(d)5(k).k.n.m) time. Lastly, we introduce an O(6(k)k!.k.n(2)) time algorithm for computing a temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance.

关键词： parameterized algorithms Phylogenetic networks Phylogenetic trees Hybridization number

来源：评论

学校读者我要写书评

暂无评论

MINIMUM DOMINATING SET OF QUEENS: A trivial programming exercise?

引用

DISCRETE APPLIED MATHEMATICS 2010年第4期158卷 308-318页

作者： Fernau, Henning Univ Trier FB Abt Informat 4 D-54286 Trier Germany

MINIMUM DOMINATING SET OF QUEENS is one of the typical programming exercises of a first year's computer science course. However, little work has been published on the complexity of this problem. We analyse here several algorithms and show that advanced algorithmic techniques may dramatically speed up solving this problem. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Exact algorithms parameterized algorithms N P-completeness Chess problems Domination problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：