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

arXiv 2022年

作者： Ganian, Robert Hamm, Thekla Knop, Dušan Schierreich, Šimon Suchý, Ondřej Algorithms and Complexity Group TU Wien Austria Algorithms and Complexity Group Utrecht University Netherlands Faculty of Information Technology Czech Technical University Prague Czech Republic

Hedonic diversity games are a variant of the classical hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a comprehensive parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general hedonic diversity games where the number of colors is not necessarily restricted to two, and show that—apart from two trivial cases—a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question asked in previous work (Boehmer and Elkind, AAAI 2020). Copyright © 2022, The Authors. All rights reserved.

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

A functional language for departmental metacomputing

A functional language for departmental metacomputing

引用

作者： Gava, Frédéric Loulergue, Frédéric Laboratory of Algorithms Complexity and Logic Créteil France

We have designed a functional data-parallel language called BSML for programming bulk synchronous parallel (BSP) algorithms. Deadlocks and indeterminism are avoided and the execution time can be then estimated. For very large scale applications more than one parallel machine could be needed. One speaks about metacomputing. A major problem in programming application for such architectures is their hierarchical network structures: latency and bandwidth of the network between parallel nodes could be orders of magnitude worse than those inside a parallel node. Here we consider how to extend both the BSP model and BSML, well-suited for parallel computing, in order to obtain a model and a functional language suitable for metacomputing. ©World Scientific Publishing Company.

关键词： Parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

The Fine-Grained complexity of Graph Homomorphism Parameterized by Clique-Width 49

The Fine-Grained Complexity of Graph Homomorphism Parameteri...

引用

49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022

作者： Ganian, Robert Hamm, Thekla Korchemna, Viktoriia Okrasa, Karolina Simonov, Kirill Algorithms and Complexity Group TU Wien Austria Faculty of Matematics and Information Science Warsaw University of Technology Poland Faculty of Mathematics Informatics and Mechanics University of Warsaw Poland

ISBN: (纸本)9783959772358

The generic homomorphism problem, which asks whether an input graph G admits a homomorphism into a fixed target graph H, has been widely studied in the literature. In this article, we provide a fine-grained complexity classification of the running time of the homomorphism problem with respect to the clique-width of G (denoted cw) for virtually all choices of H under the Strong Exponential Time Hypothesis. In particular, we identify a property of H called the signature number s(H) and show that for each H, the homomorphism problem can be solved in time O∗(s(H)cw). Crucially, we then show that this algorithm can be used to obtain essentially tight upper bounds. Specifically, we provide a reduction that yields matching lower bounds for each H that is either a projective core or a graph admitting a factorization with additional properties - allowing us to cover all possible target graphs under long-standing conjectures. © Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and Kirill Simonov;licensed under Creative Commons License CC-BY 4.0

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

The complexity of Optimizing Atomic Congestion

arXiv

引用

arXiv 2023年

作者： Brand, Cornelius Ganian, Robert Kalyanasundaram, Subrahmanyam Inerney, Fionn Mc Algorithms & Complexity Theory Group Regensburg University Germany Algorithms and Complexity Group TU Wien Austria Department of Computer Science and Engineering IIT Hyderabad India

Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies—that is, a centrally planned routing that minimizes the average cost of agents—is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem. Copyright © 2023, The Authors. All rights reserved.

关键词： Separators

来源：评论

学校读者我要写书评

暂无评论

New complexity-theoretic frontiers of tractability for neural network training 23

New complexity-theoretic frontiers of tractability for neura...

引用

Proceedings of the 37th International Conference on Neural Information Processing Systems

作者： Cornelius Brand Robert Ganian Mathis Rocton Algorithms & Complexity Group Vienna University of Technology Vienna Austria

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of 1, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Minimizing Switches in Cased Graph Drawings 32

Minimizing Switches in Cased Graph Drawings

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Ganian, Robert Nöllenburg, Martin Röder, Sebastian Algorithms and Complexity Group TU Wien Austria TU Wien Austria

ISBN: (纸本)9783959773430

In cased drawings of graphs, edges are drawn in front of others in order to decrease the negative impact of crossings on readability. In this context, a switch on an edge is defined as two consecutive crossings, where the edge is drawn in the front at one crossing and behind another edge at the next crossing. We investigate the problem of minimizing the maximum number of switches on any edge - both in a fixed drawing as well as for non-embedded graphs. We resolve an open question by Eppstein, van Kreveld, Mumford, and Speckmann (2009) by establishing the NP-hardness of minimizing the number of switches in a fixed drawing, provide a fixed-parameter algorithm for this problem, and obtain a full characterization of the problem for non-embedded graphs. © Robert Ganian, Martin Nöllenburg, and Sebastian Röder.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Constrained Boundary Labeling 35

Constrained Boundary Labeling

引用

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Algorithms and Complexity Group TU Wien Austria Algorithms cluster TU Eindhoven Netherlands Technical University of Munich Germany

ISBN: (纸本)9783959773546

Boundary labeling is a technique in computational geometry used to label dense sets of feature points in an illustration. It involves placing labels along an axis-aligned bounding box and connecting each label with its corresponding feature point using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Finally, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. © Thomas Depian, Martin Nöllenburg, Soeren Terziadis, and Markus Wallinger.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

GdMetriX - A NetworkX Extension For Graph Drawing Metrics 32

GdMetriX - A NetworkX Extension For Graph Drawing Metrics

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Nöllenburg, Martin Röder, Sebastian Wallinger, Markus Algorithms and Complexity Group TU Wien Austria TU Wien Austria Chair for Efficient Algorithms Technical University of Munich Germany

ISBN: (纸本)9783959773430

networkX is a well-established Python library for network analysis. With gdMetriX, we aim to extend the functionality of networkX and provide common quality metrics used in the field of graph drawing, such as the number of crossings or the angular resolution. In addition, the package provides easy-to-use access to the graph datasets provided by the 'Graph Layout Benchmark Datasets' project from the Northeastern University Visualization Lab. © Martin Nöllenburg, Sebastian Röder, and Markus Wallinger.

关键词： Data visualization

来源：评论

学校读者我要写书评

暂无评论

Hitting weighted even cycles in planar graphs 24

Hitting weighted even cycles in planar graphs

引用

24th International Conference on Approximation algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021

作者： Göke, Alexander Koenemann, Jochen Mnich, Matthias Sun, Hao Hamburg University of Technology Institute for Algorithms and Complexity Germany University of Waterloo Canada

ISBN: (纸本)9783959772075

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs. © Alexander Göke, Jochen Koenemann, Matthias Mnich, and Hao Sun;licensed under Creative Commons License CC-BY 4.0

关键词： Undirected graphs

来源：评论

学校读者我要写书评

暂无评论

Polynomial kernels for edge modification problems towards block and strictly chordal graphs

引用

Discrete Mathematics and Theoretical Computer Science 2025年 272卷

作者： Dumas, Maël Perez, Anthony Rocton, Mathis Todinca, Ioan Institute of Informatics University of Warsaw Warsaw Poland Université d’Orléans INSA CVL LIFO UR 4022 Orléans France Algorithms and Complexity Group TU Wien Vienna Austria

We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph G = (V, E) and an integer k ∈ N and seeks to edit (add or delete) at most k edges from G to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide: © 2025 by the author(s)

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：