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

Parameterized Complexity of Diameter

ALGORITHMICA 2023年第2期85卷 325-351页

作者： Bentert, Matthias Nichterlein, Andre TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

Diameter-the task of computing the length of a longest shortest path-is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no O(n(1.99))-time algorithm even in sparse graphs (Roditty L, Williams, VV in Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the 45th Symposium on Theory of Computing Conference (STOC '13), pp 515-524. ACM, 2013). To circumvent this lower bound, we investigate which parameters allow for running times of the form f (k) (n + m) where k is the respective parameter and f is a computable function. To this end, we systematically explore a hierarchy of structural graph parameters.

关键词： FPT in P multivariate algorithmics Strong exponential time hypothesis Finegrained reductions

来源：评论

学校读者我要写书评

暂无评论

Multistage graph problems on a global budget

引用

THEORETICAL COMPUTER SCIENCE 2021年 868卷 46-64页

作者： Heeger, Klaus Himmel, Anne-Sophie Kammer, Frank Niedermeier, Rolf Renken, Malte Sajenko, Andrej TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany Univ Appl Sci Mittelhessen THM Giessen Germany

Time-evolving or temporal graphs gain more and more popularity when exploring complex networks. In this context, the multistage view on computational problems is among the most natural frameworks. Roughly speaking, herein one studies the different (time) layers of a temporal graph (effectively meaning that the edge set may change over time, but the vertex set remains unchanged), and one searches for a solution of a given graph problem for each layer. The twist in the multistage setting is that the solutions found must not differ too much between subsequent layers. We relax on this already established notion by introducing a global instead of the local budget view studied so far. More specifically, we allow for few disruptive changes between subsequent layers but request that overall, that is, summing over all layers, the degree of change is moderate. Studying several classical graph problems (both NP-hard and polynomial-time solvable ones) from a parameterized complexity angle, we encounter both fixed-parameter tractability and parameterized hardness results. Surprisingly, we find that sometimes the global multistage versions of NP-hard problems such as VERTEX COVER turn out to be computationally more tractable than the ones of polynomial-time solvable problems such as MATCHING. In addition to time complexity, we also analyze the space efficiency of our algorithms. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Temporal graphs Time-varying graphs NP-hardness Parameterized complexity multivariate algorithmics Space complexity

来源：评论

学校读者我要写书评

暂无评论

Parameterized aspects of triangle enumeration

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2019年 103卷 61-77页

作者： Bentert, Matthias Fluschnik, Till Nichterlein, Andre Niedermeier, Rolf TU Berlin Algorithm & Computat Complex Fac 4 Berlin Germany

The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration. We provide both positive results (new enumerative kernelizations, "subcubic" parameterized solving algorithms) as well as negative results (presumable uselessness in terms of "faster" parameterized algorithms of certain parameters such as graph diameter). To this end, we introduce new and extend previous concepts. (C) 2019 Elsevier Inc. All rights reserved.

关键词： FPT in P multivariate algorithmics Enumerative kernelization Hardness inside P Distance to triviality Degeneracy

来源：评论

学校读者我要写书评

暂无评论

Computing equality-free and repetitive string factorisations

引用

THEORETICAL COMPUTER SCIENCE 2016年 618卷 42-51页

作者： Schmid, Markus L. Univ Trier Fachbereich 4 Abt Informat Wissensch D-54286 Trier Germany

For a string w, a factorisation is any tuple (u(1), u(2), ..., u(k)) of strings that satisfies w = u(1).u(2) ... u(k). A factorisation is called equality-free if each two factors are different, its size is the number of factors (counting each occurrence of repeating factors) and its width is the maximum length of any factor. To decide, for a string w and a number m, whether w has an equality-free factorisation with a size of at least (or a width of at most) m are NP-complete problems. We further investigate the complexity of these problems and we also study the converse problems of computing a factorisation that is to a large extent not equality-free, i.e., a factorisation of size at least (or width at most) m such that the total number of different factors does not exceed a given bound k. (C) 2016 Elsevier B.V. All rights reserved.

关键词： String factorisations NP-hard string problems Parameterised complexity multivariate algorithmics

来源：评论

学校读者我要写书评

暂无评论

Finding Consensus Strings with Small Length Difference between Input and Solution Strings

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2017年第3期9卷 13-13页

作者： Schmid, Markus L. Univ Trier Fachbereich 4 Abt Informat D-54286 Trier Germany

The Closest Substring Problem is to decide, for given strings s(1),...,s(k) of length at most l and numbersm andd, whether there is a length-m string s and length-m substrings s(i)' of s(i), such that s has a Hamming distance of at most d from each s(i)'. If we instead require the sum of all the Hamming distances between s and each s(i)' to be bounded by d, then it is called the Consensus Patterns Problem. We contribute to the parameterised complexity analysis of these classical NP-hard string problems by investigating the parameter (l - m), i.e., the length difference between input and solution strings. For most combinations of (l - m) and one of the classical parameters (m, l, k, or d), we obtain fixed-parameter tractability. However, even for constant (l - m) and constant alphabet size, both problems remain NP-hard. While this follows from known results with respect to the Closest Substring, we need a new reduction in the case of the Consensus Patterns. As a by-product of this reduction, we obtain an exact exponential-time algorithm for both problems, which is based on an alphabet reduction.

关键词： Parameterised complexity multivariate algorithmics hard string problems

来源：评论

学校读者我要写书评

暂无评论

On explaining integer vectors by few homogeneous segments

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第4期81卷 766-782页

作者： Bredereck, Robert Chen, Jiehua Hartung, Sepp Komusiewicz, Christian Niedermeier, Rolf Suchy, Ondrej TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Czech Tech Univ Fac Informat Technol Prague Czech Republic

We extend previous studies on "explaining" a nonnegative integer vector by sums of few homogeneous segments, that is, vectors where all nonzero entries are equal and consecutive. We study two NP-complete variants which are motivated by radiation therapy and database applications. In VECTOR POSITIVE EXPLANATION, the segments may have only positive integer entries;in VECTOR EXPLANATION, the segments may have arbitrary integer entries. Considering several natural parameterizations such as the maximum vector entry y and the maximum difference 8 between consecutive vector entries, we obtain a refined picture of the computational (in-)tractability of these problems. For example, we show that VEcrox EXPLANATION is fixed-parameter tractable with respect to delta, and that, unless NP subset of coNP/poly, there is no polynomial kernelization for VECTOR POSITIVE EXPLANATION with respect to the parameter gamma. We also identify relevant special cases where VECTOR POSITIVE EXPLANATION is algorithmically harder than VECTOR EXPLANATION. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Parameterized complexity Matrix and vector decomposition multivariate algorithmics NP-hardness Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring

引用

JOURNAL OF DISCRETE ALGORITHMS 2011年第1期9卷 137-151页

作者： Komusiewicz, Christian Niedermeier, Rolf Uhlmann, Johannes Friedrich Schiller Univ Jena Inst Informat Ernst Abbe Pl 2 D-07743 Jena Germany

The NP-hard Interval Constrained Coloring (ICC) problem appears in the interpretation of experimental data in biochemistry dealing with protein fragments. Given a set of m integer intervals in the range 1 to n and a set of m associated multisets of colors (specifying for each interval the colors to be used for its elements), one asks whether there is a "consistent" coloring for all integer points from {1,..., n} that complies with the constraints specified by the color multisets. We thoroughly analyze a known NP-hardness proof for ICC. In this way, we identify numerous parameters that naturally occur in ICC and strongly influence its practical solvability. Accordingly, we present several positive (fixed-parameter) tractability results exploiting various parameterizations. We substantiate the usefulness of this "multivariate algorithmics approach" by presenting experimental results with real-world data. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Interval constraint coloring Parametrized complexity multivariate algorithmics NP-hard problem Experiments

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：