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

Finding paths of length k in O*(2^k) time

INFORMATION PROCESSING LETTERS 2009年第6期109卷 315-318页

作者： Williams, Ryan Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

We give a randomized algorithm that determines if a given graph has a simple path of length at least k in O(2(k) . poly(n)) time. Our method extends a recent O(2(3k/2). poly(n)) <= 0 (2.83(k) . poly(n)) algorithm o... 详细信息

关键词： Randomized algorithms parameterized algorithms Graph algorithms Group algebra

来源：评论

学校读者我要写书评

暂无评论

On the kernel size of clique cover reductions for random intersection graphs

引用

JOURNAL OF DISCRETE algorithms 2015年 34卷 128-136页

作者： Friedrich, Tobias Hercher, Christian Hasso Plattner Inst Potsdam Germany Univ Jena D-07745 Jena Germany

Covering all edges of a graph by a minimum number of cliques is a well known NP-hard problem. For the parameter k being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case. We study the average kernel size for random intersection graphs with n vertices, edge probability p, and clique covers of size k. We consider the well-known set of reduction rules of Gramm, Guo, Huffner, and Niedermeier (2009)[17] and show that with high probability they reduce the graph completely if pis bounded away from 1 and k < c log n for some constant c > 0. This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Clique cover Kernelization Average case Random intersection graphs Erdos-Renyi graphs

来源：评论

学校读者我要写书评

暂无评论

Constrained multilinear detection for faster functional motif discovery

引用

INFORMATION PROCESSING LETTERS 2012年第22期112卷 889-892页

作者： Koutis, Ioannis Univ Puerto Rico Dept Comp Sci Rio Piedras PR 00931 USA

The GRAPH MOTIF problem asks whether a given multiset of colors appears on a connected subgraph of a vertex-colored graph. The fastest known parameterized algorithm for this problem is based on a reduction to the k-Multilinear Detection (k-MLD) problem: the detection of multilinear terms of total degree k in polynomials presented as circuits. We revisit k-MLD and define k-CMLD, a constrained version of it which reflects GRAPH MOTIF more faithfully. We then give a fast algorithm for k-CMLD. As a result we obtain faster parameterized algorithms for GRAPH MOTIF and variants of it. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Randomized algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Subexponential algorithms for partial cover problems

引用

INFORMATION PROCESSING LETTERS 2011年第16期111卷 814-818页

作者： Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket Inst Math Sci Madras 600113 Tamil Nadu India Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif San Diego Dept CS & Engn San Diego CA 92103 USA

Partial Cover problems are optimization versions of fundamental and well-studied problems like VERTEX COVER and DOMINATING SET. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number k of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by k. It was recently shown by Amini et al. (2008) [1] that PARTIAL VERTEX COVER and PARTIAL DOMINATING SET are fixed parameter tractable on large classes of sparse graphs, namely H-minor-free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time 2(O(k))n(O(1)). During the last decade there has been an extensive study on parameterized subexponential algorithms. In particular, it was shown that the classical VERTEX COVER and DOMINATING SET problems can be solved in subexponential time on H-minor-free graphs. The techniques developed to obtain subexponential algorithms for classical problems do not apply to partial cover problems. It was left as an open problem by Amini et al. (2008) [1] whether there is a subexponential algorithm for PARTIAL VERTEX COVER and PARTIAL DOMINATING SET. In this paper, we answer the question affirmatively by solving both problems in time 2(O(root k))n(O(1)) not only on planar graphs but also on much larger classes of graphs, namely, apex-minor-free graphs. Compared to previously known algorithms for these problems our algorithms are significantly faster and simpler. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized algorithms Subexponential algorithms Partial cover problems Partial Dominating Set

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Distortion is Fixed Parameter Tractable

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2013年第4期5卷 1–20页

作者： Fellows, Michael Fomin, Fedor V. Lokshtanov, Daniel Losievskaja, Elena Rosamond, Frances Saurabh, Saket Charles Darwin Univ Darwin NT Australia Univ Bergen Dept Informat Bergen Norway Univ Iceland Dept Comp Sci Reykjavik Iceland Inst Math Sci Madras Tamil Nadu India

We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M(G) be the shortest path metric of an edge-weighted graph G, with the vertex set V(G) and the edge set E(G), on n vertices. We give the first fixed parameter tractable algorithm that for an unweighted graph metric M and integer d either constructs an embedding of M into the line with distortion at most d, or concludes that no such embedding exists. Our algorithm requires O(nd(4)(2d + 1)(2d)) time which is a significant improvement over the best previous algorithm that runs in time O(n(4d+2)d(O(1))). Because of its apparent similarity to the notoriously hard BANDWIDTH MINIMIZATION problem, we find it surprising that this problem turns out to be fixed parameter tractable. We extend our results on embedding unweighted graph metric into the line in two ways. First, we give an algorithm to construct small-distortion embeddings of weighted graph metrics. The running time of our algorithm is O(n(dW)(4)(2d + 1)(2dW)), where W is the largest edge weight of the input graph. To complement this result, we show that the exponential dependence on the maximum edge weight is unavoidable. In particular, we show that deciding whether a weighted graph metric M(G) with maximum weight W < vertical bar V(G)vertical bar can be embedded into the line with distortion at most d is NP-complete for every fixed rational d >= 2. This rules out any possibility of an algorithm with running time O((nW)(h(d))) where h is a function of d alone. Second, we consider more general host metrics for which analogous results hold. In particular, we prove that for any tree T with maximum degree Delta, embedding M into a shortest path metric of T is fixed parameter tractable, parameterized by (Delta, d).

关键词： algorithms Theory Embedding distortion tree parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tractable Parameterizations for the Minimum Linear Arrangement Problem

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2016年第2期8卷 1–12页

作者： Fellows, Michael R. Hermelin, Danny Rosamond, Frances Shachnai, Hadas Univ Bergen Dept Informat POB 7803 N-5020 Bergen Norway Ben Gurion Univ Negev Dept Ind Engn & Management Marcus Family CampusPOB 653 IL-8410501 Beer Sheva Israel Technion Israel Inst Technol Dept Comp Sci IL-3200003 Haifa Israel

The MINIMUM LINEAR ARRANGEMENT (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, parameterized by the treewidth of the input graph. We investigate MLA with respect to three parameters that provide more structure than treewidth. In particular, we give a factor (1+epsilon)-approximation algorithm for MLA parameterized by (epsilon, k), where k is the vertex cover number of the input graph. By a similar approach, we obtain two FPT algorithms that exactly solve MLA parameterized by, respectively, the max leaf and edge clique cover numbers of the input graph.

关键词： Minimum linear arrangement parameterized algorithms fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

algorithms for propositional model counting

引用

JOURNAL OF DISCRETE algorithms 2010年第1期8卷 50-64页

作者： Samer, Marko Szeider, Stefan Tech Univ Darmstadt Dept Comp Sci Darmstadt Germany Univ Durham Dept Comp Sci Durham England

We present algorithms for the propositional model counting problem #SAT. The algorithms utilize tree decompositions of certain graphs associated with the given CNF formula;in particular we consider primal, dual, and incidence graphs. We describe the algorithms coherently for a direct comparison and with sufficient detail for making an actual implementation reasonably easy. We discuss several aspects of the algorithms including worst-case time and space requirements. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Model counting Propositional satisfiability parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Comparing temporal graphs using dynamic time warping

引用

SOCIAL NETWORK ANALYSIS AND MINING 2020年第1期10卷 1-16页

作者： Froese, Vincent Jain, Brijnesh Niedermeier, Rolf Renken, Malte Tech Univ Berlin Fac Algorithm & Computat Complex 4 Berlin Germany Tech Univ Berlin Fac Distributed Artificial Intelligence Lab 4 Berlin Germany

Within many real-world networks, the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal graphs requires a proximity measure to compare different temporal graphs. To this end, we propose to study dynamic time warping on temporal graphs. We define the dynamic temporal graph warping (dtgw) distance to determine the dissimilarity of two temporal graphs. Our novel measure is flexible and can be applied in various application domains. We show that computing the dtgw-distance is a challenging (in general) NP-hard optimization problem and identify some polynomial-time solvable special cases. Moreover, we develop a quadratic programming formulation and an efficient heuristic. In experiments on real-world data, we show that the heuristic performs very well and that our dtgw-distance performs favorably in de-anonymizing networks compared to other approaches.

关键词： Temporal graph matching Vertex signatures Heuristic optimization Quadratic programming parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fixed parameter algorithms for ONE-SIDED CROSSING MINIMIZATION revisited

引用

JOURNAL OF DISCRETE algorithms 2008年第2期6卷 313-323页

作者： Dujmovic, Vida Fernau, Henning Kaufmann, Michael McGill Univ Dept Math & Stat Montreal PQ Canada Univ Trier FB IV Abt Informat D-54286 Trier Germany Univ Tubingen WSI Informat D-72076 Tubingen Germany

We exhibit a small problem kernel for the ONE-SIDED CROSSING MINIMIZATION problem. This problem plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we improve on the search tree algorithm developed in [V. Dujmovic, S. Whitesides, An efficient fixed parameter tractable algorithm for 1-sided crossing minimization, Algorithmica 40 (2004) 15-31] and derive an O(1.4656(k) + kn(2)) algorithm for this problem, where k upperbounds the number of tolerated edge crossings in the drawings of an n-vertex graph. (C) 2007 Elsevier B.V. All rights reserved.

关键词： Graph drawing Crossing minimization 2-layer drawings FPT parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：