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

arXiv 2025年

作者： Ganian, Robert Khazaliya, Liana Inerney, Fionn Mc Rocton, Mathis Algorithms and Complexity Group TU Wien Austria Telefónica Scientific Research Barcelona Spain

We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per concept required to successfully teach an intelligent learner under the considered, previously established model. For any class of concepts, it is known that this problem can be effortlessly transferred to the setting of balls in a graph G. We establish (1) the NP-hardness of the problem even when restricted to instances with positive non-clashing teaching dimension k = 2 and where all balls in the graph are present, (2) near-tight running time upper and lower bounds for the problem on general graphs, (3) fixed-parameter tractability when parameterized by the vertex integrity of G, and (4) a lower bound excluding fixed-parameter tractability when parameterized by the feedback vertex number and pathwidth of G, even when combined with k. Our results provide a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature. Copyright © 2025, The Authors. All rights reserved.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Worbel: Aggregating Point Labels into Word Clouds 21

Worbel: Aggregating Point Labels into Word Clouds

引用

29th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2021

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal Bhopal India Algorithms and Complexity Group Tu Wien Vienna Austria

ISBN: (纸本)9781450386647

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021 ACM.

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling

引用

ACM Journal of Experimental Algorithmics 2022年第1期27卷 1-36页

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal Bypass Road Bhauri Madhya Pradesh Bhopal462066 India TU Wien Algorithms and Complexity Group Favoritenstraße 9-11 Vienna1040 Austria

Map labeling is a classical problem in cartography and geographic information systems that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent (i.e., overlap-free) labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each timestep, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sublinear update time. Motivated by this, we study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types: (i) uniform height and width and (ii) uniform height and arbitrary width;both settings can be modeled as rectangle intersection graphs. We present the first deterministic algorithm for maintaining an MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with polylogarithmic update time. This breaks the natural barrier of update time (where is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with update time. In a subsequent algorithm, we establish the trade-off between approximation quality and update time , for . We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of unit-height and arbitrary-width rectangles with update time, where is the maximum size of an independent set of rectangles stabbed by any horizontal line. We implement our algorithms and report the results of an experimental comparison exploring the trade-off between solution quality and update time for synthetic and real-world map labeling instances. We

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

Untangling Circular Drawings: algorithms and complexity 32

Untangling Circular Drawings: Algorithms and Complexity

引用

32nd International Symposium on algorithms and Computation, ISAAC 2021

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Austria Universität Passau Germany Research Unit of Computer Graphics TU Wien Austria

ISBN: (纸本)9783959772143

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that need to be shifted to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift◦(δG) ≤ ⌊n2 ⌋ - 1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

A Structural complexity Analysis of Hierarchical Task Network Planning

arXiv

引用

arXiv 2024年

作者： Brand, Cornelius Ganian, Robert Inerney, Fion Mc Wietheger, Simon Algorithms & Complexity Theory Group Regensburg University Germany Algorithms and Complexity Group TU Wien Austria Telefónica Scientific Research Barcelona Spain

We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus lies on identifying structural properties which yield tractability. We obtain new polynomial algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Finally, we analyze the parameterized complexity of the three problems. Copyright © 2024, The Authors. All rights reserved.

关键词： Complex networks

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An improved GPU simulator for Spiking Neural P systems

An improved GPU simulator for Spiking Neural P systems

引用

6th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2011

作者： Cabarle, Francis George C. Adorna, Henry Martínez-Del-Amor, Miguel A. Algorithms and Complexity Lab. Dept. of Computer Science University of the Philippines Diliman Philippines Research Group on Natural Computing Dept. of Computer Science and AI University of Seville Spain

ISBN: (纸本)9780769545141

Spiking Neural P (SNP) systems, variants of P systems (under Membrane and Natural computing), are computing models that acquire abstraction and inspiration from the way neurons 'compute' or process information. Similar to other P system variants, SNP systems are Turing complete models that by nature compute non-deterministically and in a maximally parallel manner. P systems usually trade (often exponential) space for (polynomial to constant) time. Due to this nature, P system variants are currently limited to parallel simulations, and several variants have already been simulated in parallel devices. In this paper we present an improved SNP system simulator based on graphics processing units (GPUs). Among other reasons, current GPUs are architectured for massively parallel computations, thus making GPUs very suitable for SNP system simulation. The computing model, hardware/software considerations, and simulation algorithm are presented, as well as the comparisons of the CPU only and CPU-GPU based simulators. © 2011 IEEE.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

On the Upward Book Thickness Problem: Combinatorial and complexity Results 29th

On the Upward Book Thickness Problem: Combinatorial and Com...

引用

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

作者： Bhore, Sujoy Da Lozzo, Giordano Montecchiani, Fabrizio Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Roma Tre University Rome Italy Department of Engineering University of Perugia Perugia Italy Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are st-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP-hard for any fixed k≥ 3. We show that the problem, for any k≥ 5, remains NP-hard for graphs whose domination number is O(k), but it is FPT in the vertex cover number. © 2021, Springer Nature Switzerland AG.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：