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

2005 IEEE International Workshop on Safety, Security and Rescue Robotics

作者： Du, Jia Lei Rührup, Stefan Witkowski, Ulf Rückert, Ulrich System and Circuit Technology Research Group Heinz Nixdorf Institute University of Paderborn 33102 Paderborn Germany Algorithms and Complexity Research Group Heinz Nixdorf Institute University of Paderborn 33102 Paderborn Germany

ISBN: (纸本)078038945X

If robots are deployed in large numbers in disaster scenarios, the ability to discover and exchange resources and services with other robots in an open, heterogeneous, large-scale network will be essential for a successful operation. In this paper we present a discovery protocol that enables robots to efficiently locate resources and services available in large-scale networks. It is specifically designed for robot networks which are characterized by potentially highly dynamic network topologies and high service announcement-to-lookup ratios. The protocol exploits the position data of the robots to increase scalability and efficiency. A cell-based overlay structure is created, with master nodes in each cell. Through proactive intra-cell communication and reactive inter-cell communication, scalability is ensured and the effects of node movements on the overall network are minimized. © 2005 IEEE.

关键词： Robotics

来源：评论

学校读者我要写书评

暂无评论

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion 41

A single-exponential fixed-parameter algorithm for distance-...

引用

41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

作者： Eiben, Eduard Ganian, Robert Kwon, O-Joung Algorithms and Complexity Group TU Wien Vienna Austria Institute for Computer Science and Control Hungarian Academy of Sciences Budapest Hungary FI MU Brno Czech Republic

ISBN: (纸本)9783959770163

Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis. © Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, and Vuong A. Quyen.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Drawing k-linear Metro Maps

arXiv

引用

arXiv 2019年

作者： Nickel, Soeren Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

Schematic metro maps in practice as well as metro map layout algorithms usually adhere to an octilinear layout style with all paths composed of horizontal, vertical, and 45◦-diagonal edges. Despite growing interest in non-octilinear metro maps, generic algorithms to draw metro maps based on a system of k ≥ 2 equidistant slopes have not been investigated thoroughly. In this paper we present and implement an adaptation of the octilinear mixed-integer linear programming approach of Nöllenburg and Wolff (2011) that can draw k-linear metro maps. Copyright © 2019, The Authors. All rights reserved.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Hedonic Diversity Games: A complexity Picture with More than Two Colors

arXiv

引用

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

来源：评论

学校读者我要写书评

暂无评论

Longest Cycle above Erdos-Gallai Bound 30

Longest Cycle above Erdos-Gallai Bound

引用

30th Annual European Symposium on algorithms, ESA 2022

作者： Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Department of Informatics University of Bergen Norway St. Petersburg Department V.A. Steklov Institute of Mathematics Russia Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772471

In 1959, Erdos and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2O(k) nO(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G) + k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

On Balanced Coloring Games in Random Graphs

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 425-430页

作者： Gugelmann, Luca Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

Consider the balanced Ramsey game, in which a player has r colors and where in each round r random edges of an initially empty graph on n vertices are presented. The player has to immediately assign a different color to each edge and her goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. The Achlioptas game is similar, but the player only loses when she creates a copy of F in one distinguished color. We show that there is an infinite family of nonforests F for which the balanced Ramsey game has a different threshold than the Achlioptas game, settling an open question by Krivelevich et al. We also consider the natural vertex analogues of both games and show that their thresholds coincide for all graphs F, in contrast to our results for the edge case. © 2011 Elsevier B.V.

关键词： Coloring games Ramsey theory Random graphs

来源：评论

学校读者我要写书评

暂无评论

Multiplicative approximations and the hypervolume indicator

Multiplicative approximations and the hypervolume indicator

引用

11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

作者： Friedrich, Tobias Horoba, Christian Neumann, Frank Algorithms Group International Computer Science Institute Berkeley CA United States Fakultät für Informatik LS 2 Technische Universität Dortmund Dortmund Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarbrücken Germany

ISBN: (纸本)9781605583259

Indicator-based algorithms have become a very popular approach to solve multi-objective optimization problems. In this paper, we contribute to the theoretical understanding of algorithms maximizing the hypervolume for a given problem by distributing μ points on the Pareto front. We examine this common approach with respect to the achieved multiplicative approximation ratio for a given multi-objective problem and relate it to a set of μ points on the Pareto front that achieves the best possible approximation ratio. For the class of linear fronts and a class of concave fronts, we prove that the hypervolume gives the best possible approximation ratio. In addition, we examine Pareto fronts of different shapes by numerical calculations and show that the approximation computed by the hypervolume may differ from the optimal approximation ratio. Copyright 2009 ACM.

关键词： Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

On the path-avoidance vertex-coloring game

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 657-662页

作者： Mütze, Torsten Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

For any graph F and any integer r≥2, the online vertex-Ramsey density of F and r, denoted m*(F, r), is a parameter defined via a deterministic two-player Ramsey-type game (Painter vs. Builder). This parameter was int... 详细信息

For any graph F and any integer r≥2, the online vertex-Ramsey density of F and r, denoted m^*(F, r), is a parameter defined via a deterministic two-player Ramsey-type game (Painter vs. Builder). This parameter was introduced in a recent paper [Mütze, T., T. Rast and R. Spöhel, Coloring random graphs online without creating monochromatic subgraphs, in: Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete algorithms (SODA '11), 2011, pp. 145-158], where it was shown that the online vertex-Ramsey density determines the threshold of a similar probabilistic one-player game (Painter vs. the binomial random graph G_n,p). For a large class of graphs F, including cliques, cycles, complete bipartite graphs, hypercubes, wheels, and stars of arbitrary size, a simple greedy strategy is optimal for Painter and closed formulas for m^*(F, r) are *** this work we show that in the innocent-looking case where F=P_ℓ is a (long) path, the picture is very different. As it turns out, for this family of graphs the greedy strategy fails quite badly, and the parameter m^*(F, r) exhibits a much more complex behavior than one might expect in view of the other examples mentioned. © 2011 Elsevier B.V.

关键词： Online process Ramsey property Random graph

来源：评论

学校读者我要写书评

暂无评论

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 power of cut-based parameters for computing edge disjoint paths

arXiv

引用

arXiv 2018年

作者： Ganian, Robert Ordyniak, Sebastian Algorithms and Complexity group TU Wien Vienna Austria Algorithms group University of Sheffield Sheffield United Kingdom

This paper revisits the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in P in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter treecut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded treecut width. Our second result shows that EDP parameterized by treecut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph. Copyright © 2018, The Authors. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：