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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Unit Disk Representations of Embedded Trees, Outerplanar and Multi-legged Graphs 29th

Unit Disk Representations of Embedded Trees, Outerplanar an...

引用

29th International Symposium on Graph Drawing and Network Visualization, GD 2021

作者： Bhore, Sujoy Löffler, Maarten Nickel, Soeren Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Department of Computing and Information Sciences Utrecht University Utrecht Netherlands Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP -hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that it can be decided in linear time if a lobster graph admits a weak UDC, which permits intersections between disks of non-adjacent vertices. © 2021, Springer Nature Switzerland AG.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Evaluation of labeling strategies for rotating maps

引用

ACM Journal of Experimental Algorithmics 2016年第2期21卷 1.4-1.4页

作者： Gemsa, Andreas Nöllenburg, Martin Rutter, Ignaz Institute of Theoretical Informatics Karlsruhe Institute of Technology Am Fasanengarten 5 Karlsruhe 76131 Germany Algorithms and Complexity Group (E186/1) TU Wien Favoritenstraße 9-11 Vienna 1040 Austria

We consider the following problem of labeling points in a dynamicmap that allows *** are given a set of feature points in the plane labeled by a set of mutually disjoint labels, where each label is an axis-aligned rectangle attached with one corner to its respective point. We require that each label remains horizontally aligned during the map rotation, and our goal is to find a set of mutually nonoverlapping visible labels for every rotation angle α ∈ [0, 2π) so that the number of visible labels over a fullmap rotation of 2π is maximized. We discuss and experimentally evaluate several labeling strategies that define additional consistency constraints on label visibility to reduce flickering effects during monotone map rotation. We introduce three heuristic algorithms and compare them experimentally to an existing approximation algorithm and exact solutions obtained from an integer linear program. Our results show that on the one hand, low flickering can be achieved at the expense of only a small reduction in the objective value, and on the other hand, the proposed heuristics achieve a high labeling quality significantly faster than the other methods. © 2016 ACM.

关键词： Consistency model Dynamic map labeling Experimental evaluation Map rotations

来源：评论

学校读者我要写书评

暂无评论

Resource and service discovery for large-scale robot networks in disaster scenarios

Resource and service discovery for large-scale robot network...

引用

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 (3/2 + 1/e)-Approximation Algorithm for Ordered TSP 27

A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP

引用

27th International Conference on Approximation algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024

作者： Armbruster, Susanne Mnich, Matthias Nägele, Martin Research Institute for Discrete Mathematics Hausdorff Center for Mathematics University of Bonn Germany Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Mathematics ETH Zurich Zurich Switzerland

ISBN: (纸本)9783959773485

We present a new (3/2+1/e)-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classic metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately 1.868 holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of 5/2 for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction. © Susanne Armbruster, Matthias Mnich, and Martin Nägele.

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized algorithms 47

Long Cycles in Graphs: Extremal Combinatorics Meets Paramete...

引用

47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022

ISBN: (纸本)9783959772563

We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d > 1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdos-Gallai from 1959, states that a graph G with the average vertex degree D > 1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems, to decide whether a 2-connected graph contains a cycle of length at least 2d + k or of a cycle of length at least D + k, is fixed-parameter tractable parameterized by k. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Minimum Link Fencing 33

Minimum Link Fencing

引用

33rd International Symposium on algorithms and Computation, ISAAC 2022

作者： Bhore, Sujoy Klute, Fabian Löffler, Maarten Nöllenburg, Martin Terziadis, Soeren Villedieu, Anaïs Department of Computer Science & Engineering Indian Institute of Technology Bombay India Department of Information and Computing Sciences Utrecht University Netherlands Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772587

We study a variant of the geometric multicut problem, where we are given a set P of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where P contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of P \ {Q} does not intersect Q. © Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5 51

The k-Opt Algorithm for the Traveling Salesman Problem Has E...

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Heimann, Sophia Hoang, Hung P. Hougardy, Stefan Research Institute for Discrete Mathematics University of Bonn Germany Algorithms and Complexity Group Faculty of Informatics TU Wien Austria Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics University of Bonn Germany

ISBN: (纸本)9783959773225

The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the k-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the k-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires k 1000 and has a substantial gap. We show the two properties above for a much smaller value of k, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for k ≥ 17 and the exponential running time for k ≥ 5. © Sophia Heimann, Hung P. Hoang, and Stefan Hougardy.

关键词： Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：