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

Structural Parameterizations of Clique Coloring

ALGORITHMICA 2022年第2期84卷 273-303页

作者： Jaffke, Lars Lima, Paloma T. Philip, Geevarghese Univ Bergen Bergen Norway Chennai Math Inst Chennai Tamil Nadu India UMI ReLaX Chennai Tamil Nadu India

A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed q >= 2, we give an O(q(tw))-time algorithm when the input graph is given together with one of its tree decompositions of width tw. We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore showthat (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width.

关键词： Clique coloring parameterized algorithms Clique-width Treewidth

来源：评论

学校读者我要写书评

暂无评论

Determination of Glycan Structure from Tandem Mass Spectra

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第4期8卷 976-986页

作者： Boecker, Sebastian Kehr, Birte Rasche, Florian Univ Jena Fac Math & Comp Sci Chair Bioinformat D-07743 Jena Germany Inst Comp Sci Algorithm Bioinformat Grp D-14195 Berlin Germany

Glycans are molecules made from simple sugars that form complex tree structures. Glycans constitute one of the most important protein modifications and identification of glycans remains a pressing problem in biology. Unfortunately, the structure of glycans is hard to predict from the genome sequence of an organism. In this paper, we consider the problem of deriving the topology of a glycan solely from tandem mass spectrometry (MS) data. We study, how to generate glycan tree candidates that sufficiently match the sample mass spectrum, avoiding the combinatorial explosion of glycan structures. Unfortunately, the resulting problem is known to be computationally hard. We present an efficient exact algorithm for this problem based on fixed-parameter algorithmics that can process a spectrum in a matter of seconds. We also report some preliminary results of our method on experimental data, combining it with a preliminary candidate evaluation scheme. We show that our approach is fast in applications, and that we can reach very well de novo identification results. Finally, we show how to count the number of glycan topologies for a fixed size or a fixed mass. We generalize this result to count the number of (labeled) trees with bounded out degree, improving on results obtained using Polya's enumeration theorem.

关键词： Computational mass spectrometry glycans parameterized algorithms exact algorithms counting trees

来源：评论

学校读者我要写书评

暂无评论

Improved exact algorithms for M_AX-S_AT

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期142卷 17-27页

作者： Chen, JE Kanj, IA Depaul Univ Sch CTI Chicago IL 60604 USA Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the maximum number of clauses in time O(1.3247(m)\F\), where m is the number of clauses in F, and \F\ is the sum of the number of literals appearing in each clause in F. Moreover, given a parameter k, we give an O(1.3695(k) + \F\) parameterized algorithm that decides whether a truth assignment for F satisfying at least k clauses exists. Both algorithms improve the previous best algorithms by Bansal and Raman for the problem. (C) 2004 Elsevier B.V. All rights reserved.

关键词： maximum satisfiability exact algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards a Polynomial Kernel for Directed Feedback Vertex Set

引用

ALGORITHMICA 2021年第5期83卷 1201-1221页

作者： Bergougnoux, Benjamin Eiben, Eduard Ganian, Robert Ordyniak, Sebastian Ramanujan, M. S. Univ Bergen Bergen Norway Royal Holloway Univ London Egham Surrey England Vienna Univ Technol Vienna Austria Univ Sheffield Sheffield S Yorkshire England Univ Warwick Coventry W Midlands England Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen et al. (J ACM 55(5):177-186, 2008);since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. Since this problem has remained open in spite of the best efforts of a number of prominent researchers and pioneers in the field, a natural step forward is to study the kernelization complexity of DFVS parameterized by a natural larger parameter. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.

关键词： parameterized algorithms Kernelization (Directed) feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

Minimum fill-in and treewidth of split plus ke and split plus kv graphs

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 747-754页

作者： Mancini, Federico Univ Bergen Dept Informat N-5020 Bergen Norway

In this paper we investigate how graph problems that are NP-hard in general, but polynomial time solvable on split graphs, behave on input graphs that are close to being split. For this purpose we define split + ke and split + kv graphs to be the graphs that can be made split by removing at most k edges and at most k vertices, respectively. We show that problems like treewidth and minimum fill-in are fixed parameter tractable with parameter k on split + ke graphs. Along with positive results affixed parameter tractability of several problems on split + ke and split + kv graphs, we also show a surprising hardness result. We prove that computing the minimum fill-in of split + kv graphs is NP-hard even for k = 1. This implies that also minimum fill-in of chordal + kv graphs is NP-hard for every k. In contrast, we show that the treewidth of split + 1v graphs can be computed in linear time. This gives probably the first graph class for which the treewidth and the minimum fill-in problems have different computational complexity. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Split graphs Minimum fill-in Treewidth parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

A LINEAR FIXED PARAMETER TRACTABLE ALGORITHM FOR CONNECTED PATHWIDTH

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 411-435页

作者： Kante, Mamadou M. Paul, Christophe Thilikos, Dimitrios M. Univ Clermont Auvergne CNRS LIMOS Clermont Ferrand France Univ Montpellier CNRS LIRMM Montpellier France

The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search, where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy are to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable;in particular we design a 2(O)((k2)) .n time algorithm that checks whether the connected pathwidth of G is at most k. This resolves an open question by Dereniowski, Osula, and Rzplewski [Theoret. Comput. Sci., 794 (2019), pp. 85-100]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced by Bodlaender and Kloks [J. algorithms, 21 (1996), pp. 358-402] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a "global" demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immedi

关键词： parameterized algorithms graph theory width parameter graph decomposition cops and robber game

来源：评论

学校读者我要写书评

暂无评论

Complexity of modification problems for reciprocal best match graphs

引用

THEORETICAL COMPUTER SCIENCE 2020年 809卷 384-393页

作者： Hellmuth, Marc Geiss, Manuela Stadler, Peter F. Univ Leipzig Bioinformat Grp Dept Comp Sci Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Ernst Moritz Arndt Univ Greifswald Dept Math & Comp Sci Walther Rathenau Str 47 D-17487 Greifswald Germany Saarland Univ Ctr Bioinformat Bldg E 2-1POB 151150 D-66041 Saarbrucken Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Univ Vienna Inst Theoret Chem F Wahringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

Reciprocal best match graphs (RBMGs) are vertex colored graphs whose vertices represent genes and the colors the species where the genes reside. Edges identify pairs of genes that are most closely related with respect to an underlying evolutionary tree. In practical applications this tree is unknown and the edges of the RBMGs are inferred by quantifying sequence similarity. Due to noise in the data, these empirically determined graphs in general violate the condition of being a "biologically feasible" RBMG. Therefore, it is of practical interest in computational biology to correct the initial estimate. Here we consider deletion (remove at most k edges) and editing (add or delete at most k edges) problems. We show that the decision version of the deletion and editing problem to obtain RBMGs from vertex colored graphs is NP-hard. Using known results for the so-called bicluster editing, we show that the RBMG editing problem for 2-colored graphs is fixed-parameter tractable. A restricted class of RBMGs appears in the context of orthology detection. These are cographs with a specific type of vertex coloring known as hierarchical coloring. We show that the decision problem of modifying a vertex-colored graph (either by edge-deletion or editing) into an RBMG with cograph structure or, equivalently, to an hierarchically colored cograph is NP-complete. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Reciprocal best matches Hierarchically colored cographs Orthology relation Bicluster graph Editing NP-hardness parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential algorithms

引用

ALGORITHMICA 2011年第4期60卷 987-1003页

作者： Koutsonas, Athanassios Thilikos, Dimitrios M. Univ Athens Athens 15784 Greece

The Planar Feedback Vertex Set problem asks whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard techniques from parameterized algorithm design indicate that both problems can be solved by sub-exponential parameterized algorithms (where k is the parameter). In this paper we improve the algorithmic analysis of both problems by proving a series of combinatorial results relating the branchwidth of planar graphs with their face cover. Combining this fact with duality properties of branchwidth, allows us to derive analogous results on feedback vertex set. As a consequence, it follows that Planar Feedback Vertex Set and Face Cover can be solved in O(2(15.11).root(k) + n(2)) and O(2(10.1).root(k) + n(2)) steps, respectively.

关键词： Branchwidth parameterized algorithms Feedback vertex set Face cover

来源：评论

学校读者我要写书评

暂无评论

A faster fixed parameter algorithm for two-layer crossing minimization

引用

INFORMATION PROCESSING LETTERS 2016年第9期116卷 547-549页

作者： Kobayashi, Yasuaki Tamaki, Hisao Gakushuin Univ Toshima Ku 1-5-1 Mejiro Tokyo 1718588 Japan Meiji Univ Tama Ku 1-1-1 Higashimita Kawasaki Kanagawa 2148571 Japan Kyoto Univ Sakyo Ku Kyoto 6068501 Japan

We give an algorithm that decides whether the bipartite crossing number of a given graph is at most k. The running time of the algorithm is upper bounded by 2(O(k)) + n(O(1)), where n is the number of vertices of the input graph, which improves the previously known algorithm due to Kobayashi et al. (TCS 2014) that runs in 2(O(klogk)) + n(O(1)) time. This result is based on a combinatorial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Bipartite crossing number Graph algorithms Graph drawing parameterized algorithms Two-layer crossing minimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：