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

On the Relation of Strong Triadic Closure and Cluster Deletion

ALGORITHMICA 2020年第4期82卷 853-880页

作者： Gruettemeier, Niels Komusiewicz, Christian Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany

We study the parameterized and classical complexity of two problems that are concerned with induced paths on three vertices, called P(3)s, in undirected graphs G = ( V, E). In Strong Triadic Closure we aim to label the edges in E as strong and weak such that at most k edges are weak and G contains no induced P-3 with two strong edges. In Cluster Deletion we aim to destroy all induced P3s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a 4k-vertex kernel. Then, we study parameterization by l := |E|- k and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to l. Finally, we give a dichotomy of the classical complexity of both problems on H-free graphs for all H of order at most four.

关键词： Social networks fixed-parameter algorithms Kernelization Graph classes

来源：评论

学校读者我要写书评

暂无评论

On the tractability of finding disjoint clubs in a network

引用

THEORETICAL COMPUTER SCIENCE 2019年 777卷 243-251页

作者： Dondi, Riccardo Mauri, Giancarlo Zoppis, Italo Univ Bergamo Dipartimento Lettere Filosofia Comunicaz Bergamo Italy Univ Milano Bicocca DISCo Milan Italy

We study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k vertices of the network. An s-club is a connected graph that has diameter bounded by s, for a positive integer s. We demand that each club is non-trivial, that is it has order at least t >= 2, for some positive integer t. We prove that the problem is APX-hard even when the input graph has bounded degree, s = 2, t = 3 and r = vertical bar V vertical bar. Moreover, we show that the problem is polynomial-time solvable when s >= 4, t = 3 and r = vertical bar V vertical bar, and when s >= 3, t = 2 and r = vertical bar V vertical bar. Finally, for s >= 2, we present a fixed-parameter algorithm for the problem, when parameterized by the number of covered vertices. (C) 2019 Elsevier B.V. All rights reserved.

关键词： s-Clubs Graph problems APX-hardness Graph algorithms fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards an algorithmic guide to Spiral Galaxies

引用

THEORETICAL COMPUTER SCIENCE 2015年 586卷 26-39页

作者： Fertin, Guillaume Jamshidi, Shahrad Komusiewicz, Christian Univ Nantes LINA CNRS UMR 6241 F-44035 Nantes France TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

We study the one-player game SPIRAL GALAXIES from an algorithmic viewpoint. SPIRAL GALAXIES has been shown to be NP-hard [6] more than a decade ago, but so far it seems that no one has dared exploring its algorithmic ... 详细信息

关键词： NP-hard problems fixed-parameter algorithms One-player game

来源：评论

学校读者我要写书评

暂无评论

Myhill-Nerode Methods for Hypergraphs

引用

ALGORITHMICA 2015年第4期73卷 696-729页

作者： van Bevern, Rene Downey, Rodney G. Fellows, Michael R. Gaspers, Serge Rosamond, Frances A. TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Victoria Univ Wellington Wellington New Zealand Charles Darwin Univ Sch Engn & IT Darwin NT 0909 Australia Univ New S Wales Sydney NSW Australia NICTA Sydney NSW Australia

We give an analog of the Myhill-Nerode theorem from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems. (1) We provide an algorithm for testing whether a hypergraph has cutwidth at most that runs in linear time for constant . In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by . (2) We show that it is not expressible in monadic second-order logic whether a hypergraph has bounded (fractional, generalized) hypertree width. The proof leads us to conjecture that, in terms of parameterized complexity theory, these problems are W[1]-hard parameterized by the incidence treewidth (the treewidth of the incidence graph). Thus, in the form of the Myhill-Nerode theorem for hypergraphs, we obtain a method to derive linear-time algorithms and to obtain indicators for intractability for hypergraph problems parameterized by incidence treewidth.

关键词： NP-hard problems fixed-parameter algorithms Automata theory Cutwidth Hypertree width

来源：评论

学校读者我要写书评

暂无评论

Measuring what matters: A hybrid approach to dynamic programming with treewidth

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 121卷 57-75页

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Kwon, O-joung Royal Holloway Univ London Dept Comp Sci Egham Surrey England Vienna Univ Technol Dept Comp Sci Vienna Austria Incheon Natl Univ Dept Math Incheon South Korea Inst Basic Sci IBS Discrete Math Grp Daejeon South Korea

We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for CHROMATIC NUMBER, HAMILTONIAN CYCLE, and MAX-CUT. (C) 2021 The Author(s). Published by Elsevier Inc.

关键词： parameterized complexity Treewidth Rank-width fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for computing the tree edit distance between unordered trees

引用

THEORETICAL COMPUTER SCIENCE 2011年第4-5期412卷 352-364页

作者： Akutsu, Tatsuya Fukagawa, Daiji Takasu, Atsuhiro Tamura, Takeyuki Kyoto Univ Inst Chem Res Bioinformat Ctr Kyoto 6110011 Japan Natl Inst Informat Tokyo 1018430 Japan

This paper presents a fixed-parameter algorithm for the tree edit distance problem for unordered trees under the unit cost model that works in O(2.62(k) . poly(n)) time and O(n(2)) space, where the parameter k is the maximum bound of the edit distance and n is the maximum size of input trees. This paper also presents polynomial-time algorithms for the case where the maximum degree of the largest common subtree is bounded by a constant. (c) 2010 Elsevier B.V. All rights reserved.

关键词： Tree edit distance fixed-parameter algorithms Dynamic programming Unordered trees

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms algorithms for recognizing monopolar and 2-subcolorable graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2018年 92卷 22-47页

作者： Kanj, Iyad Komusiewicz, Christian Sorge, Manuel van Leeuwen, Erik Jan Depaul Univ Sch Comp Chicago IL 60604 USA Friedrich Schiller Univ Jena Inst Informat Jena Germany TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands

A graph G is a (Pi(A), Pi(B))-graph if v(G) can be bipartitioned into A and B such that G[A] satisfies property Pi(A) and G[B] satisfies property Pi(B). The (Pi(A), Pi(B))-RECOGNITION problem is to recognize whether a given graph is a (Pi(A), Pi(B))-graph. There are many (Pi(A), Pi(B))-RECOGNITION problems, including the recognition problems for bipartite, split, and unipolar graphs. We present efficient algorithms for many cases of (Pi(A), Pi(B))-RECOGNITION based on a technique which we dub inductive recognition. In particular, we give fixed-parameter algorithms for two NP-hard (Pi(A), Pi(B))-RECOGNITION problems, MONOPOLAR RECOGNITION and 2-SUBCOLORING, parameterized by the number of maximal cliques in G[A]. We complement our algorithmic results with several hardness results for (Pi(A),Pi(B))-RECOGNITION. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Vertex-partition problems Graph classes Monopolar graphs Subcolorings Split graphs Unipolar graphs fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

New results for the Longest Haplotype Reconstruction problem

引用

DISCRETE APPLIED MATHEMATICS 2012年第9期160卷 1299-1310页

作者： Dondi, Riccardo Univ Bergamo Dipartimento Sci Linguaggi Comunicaz & Studi Cult I-24129 Bergamo Italy

The haplotyping problem has emerged in recent years as one of the most relevant problems in Computational Biology. In particular, in the Single Individual Haplotyping (SIN) problem, starting from a matrix of incomplete haplotype fragments, the goal is the reconstruction of the two complete haplotypes of an individual. In this paper we consider one of the variants of the Single Individual Haplotyping problem, the Longest Haplotyping Reconstruction (LHR) problem. We prove that the LHR problem is NP-hard even in the restricted case when the input matrix is error-free. Furthermore, we investigate the approximation complexity of the problem, and we show that the problem cannot be approximated within factor 2(log8) (nm) for any constant delta < 1, unless NP subset of DTIME vertical bar 2(poly) (log) (nm)vertical bar. Finally, we exhibit a fixed-parameter algorithm for the LHR problem, where the parameter is the size of the two reconstructed haplotypes. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Computational biology Haplotyping Approximation complexity fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Configurations with few crossings in topological graphs

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2007年第2期37卷 104-114页

作者： Knauer, Christian Schramm, Etienne Spillner, Andreas Wolff, Alexander Free Univ Berlin Inst Comp Sci Berlin Germany Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany Univ Jena Inst Comp Sci Jena Germany

In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph G such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees, s-t paths, cycles, matchings, and kappa-factors for kappa is an element of {1, 2). We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of k(1 - epsilon) for any epsilon > 0, where k is the number of crossings in G. We then give a simple fixed-parameter algorithm that tests in O*(2(k)) time whether G has a crossing-free configuration for any of the above, where the O*-notation neglects polynomial terms. For some configurations we have faster algorithms. The respective running times are O*(1.9999992(k)) for spanning trees and O*((root 3)(k)) for s-t paths and cycles. For spanning trees we also have an O*(1.968k)-time Monte-Carlo algorithm. Each. O*(beta(k))-time decision algorithm can be turned into an O*((beta + 1)(k))-time optimization algorithm that computes a configuration with the minimum number of crossings. (c) 2006 Elsevier B.V. All rights reserved.

关键词： topological graphs crossing minimization non-approximability approximation algorithms fixed-parameter algorithms Monte-Carlo algorithms

来源：评论

学校读者我要写书评

暂无评论

Haplotyping with missing data via perfect path phylogenies

引用

DISCRETE APPLIED MATHEMATICS 2007年第6-7期155卷 788-805页

作者： Gramm, Jens Nierhoff, Till Sharan, Roded Tantau, Till Med Univ Lubeck Inst Theoret Informat D-23538 Lubeck Germany Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Int Comp Sci Inst Berkeley CA 94704 USA Univ Tubingen Wilhelm Schickard Inst Informat D-72074 Tubingen Germany

Computational methods for inferring haplotype information from genotype data are used in studying the association between genomic variation and medical condition. Recently, Gusfield proposed a haplotype inference method that is based on perfect phylogeny principles. A fundamental problem arises when one tries to apply this approach in the presence of missing genotype data, which is common in practice. We show that the resulting theoretical problem is NP-hard even in very restricted cases. To cope with missing data, we introduce a variant of haplotyping via perfect phylogeny in which a path phylogeny is Sought. Searching for perfect path phylogenies is strongly motivated by the characteristics of human genotype data: 70% of real instances that admit a perfect phylogeny also admit a perfect path phylogeny. Our main result is a fixed-parameter algorithm for haplotyping with missing data via perfect path phylogenies. We also present a simple linear-time algorithm for the problem on complete data. (c) 2006 Elsevier B.V. All rights reserved.

关键词： haplotyping haplotypes genotypes missing data incomplete data phylogenetics perfect phylogenies path phylogenies fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：