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

parameterized Complexity of Min-Power Asymmetric Connectivity

THEORY OF COMPUTING SYSTEMS 2020年第7期64卷 1158-1182页

作者： Bentert, Matthias Haag, Roman Hofer, Christian Koana, Tomohiro Nichterlein, Andre TU Berlin Fac IV Algorithm & Computat Complex Berlin Germany

We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-weighted graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc in the chosen subgraph. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W[2]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.

关键词： Monitoring areas Reconnecting sensor networks parameterized algorithmics

来源：评论

学校读者我要写书评

暂无评论

Placing Green Bridges Optimally, with a Multivariate Analysis

引用

THEORY OF COMPUTING SYSTEMS 2024年第5期68卷 1312-1338页

作者： Fluschnik, Till Kellerhals, Leon Tech Univ Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

We study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph describing habitats or routes of wildlife animals and possibilities of building green bridges, to find a low-cost placement of green bridges that connects the habitats. We develop three problem models for this task and study them from a computational complexity and parameterized algorithmics perspective.

关键词： Wildlife crossings Computational sustainability parameterized algorithmics NP-hardness Connected subgraphs

来源：评论

学校读者我要写书评

暂无评论

Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2014年第5期28卷 721-748页

作者： Betzler, Nadja Bredereck, Robert Niedermeier, Rolf TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

Kemeny Rank Aggregation is a consensus finding problem important in many areas ranging from classical voting over web search and databases to bioinformatics. The underlying decision problem Kemeny Score is NP-complete even in case of four input rankings to be aggregated into a "median ranking". We analyze efficient polynomial-time data reduction rules with provable performance bounds that allow us to find even all optimal median rankings. We show that our reduced instances contain at most candidates where denotes the average Kendall's tau distance between the input votes. On the theoretical side, this improves a corresponding result for a "partial problem kernel" from quadratic to linear size. In this context we provide a theoretical analysis of a commonly used data reduction. On the practical side, we provide experimental results with data based on web search and sport competitions, e.g., computing optimal median rankings for real-world instances with more than 100 candidates within milliseconds. Moreover, we perform experiments with randomly generated data based on two random distribution models for permutations.

关键词： Kemeny score NP-hardness parameterized algorithmics Preprocessing Average parameterization Partial problem kernel Experiments

来源：评论

学校读者我要写书评

暂无评论

Exact combinatorial algorithms and experiments for finding maximum k-plexes

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第3期24卷 347-373页

作者： Moser, Hannes Niedermeier, Rolf Sorge, Manuel TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

We propose new practical algorithms to find maximum-cardinality k-plexes in graphs. A k-plex denotes a vertex subset in a graph inducing a subgraph where every vertex has edges to all but at most k vertices in the k-plex. Cliques are 1-plexes. In analogy to the special case of finding maximum-cardinality cliques, finding maximum-cardinality k-plexes is NP-hard. Complementing previous work, we develop exact combinatorial algorithms, which are strongly based on methods from parameterized algorithmics. The experiments with our freely available implementation indicate the competitiveness of our approach, for many real-world graphs outperforming the previously used methods.

关键词： parameterized algorithmics Social network analysis Biological network analysis NP-complete graph problems Dense subgraphs s-plexes k-dependent sets

来源：评论

学校读者我要写书评

暂无评论

The effect of homogeneity on the computational complexity of combinatorial data anonymization

引用

DATA MINING AND KNOWLEDGE DISCOVERY 2014年第1期28卷 65-91页

作者： Bredereck, Robert Nichterlein, Andre Niedermeier, Rolf Philip, Geevarghese TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Max Planck Inst Informat D-66123 Saarbrucken Germany

A matrix M is said to be k-anonymous if for each row r in M there are at least k - 1 other rows in M which are identical to r. The NP-hard k-Anonymity problem asks, given an n x m-matrix M over a fixed alphabet and an integer s > 0, whether M can be made k-anonymous by suppressing (blanking out) at most s entries. Complementing previous work, we introduce two new "data-driven" parameterizations for k-Anonymity-the number t (in) of different input rows and the number t (out) of different output rows-both modeling aspects of data homogeneity. We show that k-Anonymity is fixed-parameter tractable for the parameter t (in) , and that it is NP-hard even for t (out) = 2 and alphabet size four. Notably, our fixed-parameter tractability result implies that k-Anonymity can be solved in linear time when t (in) is a constant. Our computational hardness results also extend to the related privacy problems p-Sensitivity and a""-Diversity, while our fixed-parameter tractability results extend to p-Sensitivity and the usage of domain generalization hierarchies, where the entries are replaced by more general data instead of being completely suppressed.

关键词： k-Anonymity p-Sensitivity l-Diversity Domain generalization hierarchies Matrix modification problems parameterized algorithmics Fixed-parameter tractability NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Disentangling the Computational Complexity of Network Untangling

引用

THEORY OF COMPUTING SYSTEMS 2024年第1期68卷 103-121页

作者： Froese, Vincent Kunz, Pascal Zschoche, Philipp Tech Univ Berlin Algorithm & Computat Complex Ernst Reuter Pl 7 D-10587 Berlin Germany Humboldt Univ Algorithm Engn Rudower Chaussee 25 D-12489 Berlin Germany

We study the network untangling problem introduced by Rozenshtein et al. (Data Min. Knowl. Disc. 35(1), 213-247, 2021), which is a variant of Vertex Cover on temporal graphs-graphs whose edge set changes over discrete time steps. They introduce two problem variants. The goal is to select at most k time intervals for each vertex such that all time-edges are covered and (depending on the problem variant) either the maximum interval length or the total sum of interval lengths is minimized. This problem has data mining applications in finding activity timelines that explain the interactions of entities in complex networks. Both variants of the problem are NP-hard. In this paper, we initiate a multivariate complexity analysis involving the following parameters: number of vertices, lifetime of the temporal graph, number of intervals per vertex, and the interval length bound. For both problem versions, we (almost) completely settle the parameterized complexity for all combinations of those four parameters, thereby delineating the border of fixed-parameter tractability.

关键词： Temporal graph mining parameterized algorithmics Complexity dichotomy

来源：评论

学校读者我要写书评

暂无评论

Multivariate algorithmics for eliminating envy by donating goods

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2024年第2期38卷 1-35页

作者： Boehmer, Niclas Bredereck, Robert Heeger, Klaus Knop, Dusan Luo, Junjie Tech Univ Berlin Algorithm & Computat Complex Berlin Germany Tech Univ Clausthal Inst Informat Clausthal Zellerfeld Germany Czech Tech Univ Prague Czech Republic Beijing Jiaotong Univ Beijing Peoples R China

Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary-encoded and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

关键词： Fair allocation Indivisible resources Envy-freeness Donating goods parameterized algorithmics

来源：评论

学校读者我要写书评

暂无评论

Multistage Vertex Cover

引用

THEORY OF COMPUTING SYSTEMS 2022年第2期66卷 454-483页

作者： Fluschnik, Till Niedermeier, Rolf Rohm, Valentin Zschoche, Philipp Tech Univ Berlin Algorithm & Computat Complex Berlin Germany

The NP-complete Vertex Cover problem asks to cover all edges of a graph by a small (given) number of vertices. It is among the most prominent graph-algorithmic problems. Following a recent trend in studying temporal graphs (a sequence of graphs, so-called layers, over the same vertex set but, over time, changing edge sets), we initiate the study of Multistage Vertex Cover. Herein, given a temporal graph, the goal is to find for each layer of the temporal graph a small vertex cover and to guarantee that two vertex cover sets of every two consecutive layers differ not too much (specified by a given parameter). We show that, different from classic Vertex Cover and some other dynamic or temporal variants of it, Multistage Vertex Cover is computationally hard even in fairly restricted settings. On the positive side, however, we also spot several fixed-parameter tractability results based on some of themost natural parameterizations.

关键词： parameterized algorithmics NP-completeness Temporal graphs Data reduction

来源：评论

学校读者我要写书评

暂无评论

Separator-based data reduction for signed graph balancing

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第4期20卷 335-360页

作者： Hueffner, Falk Betzler, Nadja Niedermeier, Rolf Univ Jena Inst Informat D-07743 Jena Germany

Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.

关键词： Preprocessing Exact algorithm parameterized algorithmics Algorithm engineering Gene-regulatory network Financial network

来源：评论

学校读者我要写书评

暂无评论

Exploiting Database Management Systems and Treewidth for Counting

引用

THEORY AND PRACTICE OF LOGIC PROGRAMMING 2022年第1期22卷 128-157页

作者： Fichte, Johannes. K. K. Hecher, Markus Thier, Patrick Woltran, Stefan Univ Calif Berkeley Berkeley CA 94720 USA TU Wien Vienna Austria

Bounded treewidth is one of the most cited combinatorial invariants in the literature. It was also applied for solving several counting problems efficiently. A canonical counting problem is #Sat, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #Sat often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMSs). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMSs naturally allow for dealing with huge tables with a limited amount of main memory (RAM).

关键词： dynamic programming parameterized algorithmics bounded treewidth database systems SQL relational algebra counting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：