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

45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Klute, Fabian Nöllenburg, Martin Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria Department of Information and Computing Sciences Utrecht University Netherlands

ISBN: (纸本)9783959771597

The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph G, a connected subgraph H of G and a drawing H of H, the extension problem asks whether H can be extended into a drawing of G while maintaining some desired property of the drawing (e.g., planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when H can be obtained from G by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision algorithm. © Nathalie Bertrand;licensed under Creative Commons License CC-BY 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020).

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Further Exploiting c-Closure for FPT algorithms and Kernels for Domination Problems 39

Further Exploiting c-Closure for FPT Algorithms and Kernels ...

引用

39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022

作者： Kanesh, Lawqueen Madathil, Jayakrishnan Roy, Sanjukta Sahu, Abhishek Saurabh, Saket National University of Singapore Singapore Chennai Mathematical Institute India Algorithms and Complexity Group TU Wien Austria The Institute of Mathematical Sciences HBNI Chennai India University of Bergen Norway

ISBN: (纸本)9783959772228

For a positive integer c, a graph G is said to be c-closed if every pair of non-adjacent vertices in G have at most c - 1 neighbours in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is c-closed. The class of c-closed graphs was introduced by Fox et al. [ICALP ‘18 and SICOMP ‘20]. Koana et al. [ESA ‘20] started the study of using cl(G) as an additional structural parameter to design kernels for problems that are W-hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set and (Threshold) Dominating Set, and showed that each of these problems admits a polynomial kernel, either w.r.t. the parameter k + c or w.r.t. the parameter k for each fixed value of c. Here, k is the solution size and c = cl(G). The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable (FPT) algorithm and a polynomial kernel on c-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable w.r.t. the parameter k + cl(G), whereas Partial Dominating Set, parameterized by k is W[1]-hard even when cl(G) = 2. We also show that for each fixed c, Perfect Code admits a polynomial kernel on the class of c-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs, unless NP ⊆ co-NP/poly. © Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Fixed-Parameter algorithms for Computing RAC Drawings of Graphs

arXiv

引用

arXiv 2023年

作者： Brand, Cornelius Ganian, Robert Röder, Sebastian Schager, Florian Algorithms and Complexity Group TU Wien Vienna University of Technology Austria

In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly 90◦, where the number of bends on such polylines is typically restricted in some way. While structural and topological properties of RAC drawings have been the focus of extensive research, little was known about the boundaries of tractability for computing such drawings. In this paper, we initiate the study of RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph G with at most b bends (or determining that none exists) is fixed-parameter tractable parameterized by either the feedback edge number of G, or b plus the vertex cover number of G. © 2023, CC BY.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

A general method for computing the reachable space of mechanisms

A general method for computing the reachable space of mechan...

引用

2001 ASME Design Engineering Technical Conference and Computers and Information in Engineering Conference

作者： Fuhrmann, Artur Schömer, Elmar DaimlerChrysler Res. and Technology Virtual Reality Competence Center Ulm Germany Max-Planck-Inst. for Comp. Science Algorithms and Complexity Group Saarbrücken Germany

A new methodology is presented for computing a minimal envelope for the reachable space of a mechanism, i.e. the space that contains a given mechanism in all its admissible configurations. The research is motivated by the packaging process in Digital Mock-Up applied in automotive industry. An important task in the concept phase, the automated determination of the space requirement for all parts, is still an unsolved problem in the case of mechanisms. The particular benefit of the method presented is its generality and robustness: It is able to deal with both open- and closed-loop mechanisms. The reachable space is computed with regard to the geometric description of each part. The approximation is enclosing and always converges in a uniform way and the tolerance can be pre-defined by the user. The method combines the use of bounding object hierarchies and the application of interval analysis. It is also able to approximate the swept volume of an object following a parameterized trajectory. We describe how the efficiency can be improved by lazy evaluation and by a deeper problem analysis. The presented algorithms are implemented and tested to a large extent.

关键词： Manipulators

来源：评论

学校读者我要写书评

暂无评论

Network Navigation with Online Delays is PSPACE-complete

arXiv

引用

arXiv 2023年

作者： Depian, Thomas Kern, Christoph Röder, Sebastian Terziadis, Soeren Wallinger, Markus TU Wien Austria Algorithms & Complexity Group TU Wien Austria

In public transport networks disruptions may occur and lead to travel delays. It is thus interesting to determine whether a traveler can be resilient to delays that occur unexpectedly, ensuring that they can reach their destination in time regardless. We model this as a game between the traveler and a delay-introducing adversary. We study the computational complexity of the problem of deciding whether the traveler has a winning strategy in this game. Our main result is that this problem is PSPACE-complete. © 2023, CC BY-SA.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Hot off the Press: The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem

Hot off the Press: The First Proven Performance Guarantees f...

引用

2024 Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion

作者： Cerf, Sacha Doerr, Benjamin Hebras, Benjamin Kahane, Yakob Wietheger, Simon École Polytechnique Institut Polytechnique de Paris Paris France École Polytechnique CNRS Institut Polytechnique de Paris Palaiseau France Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9798400704956

Recently, the first mathematical runtime guarantees have been obtained for the NSGA-II, one of the most prominent multi-objective optimization algorithms, however only for synthetic benchmark *** this work, we give the first proven performance guarantees for a classic optimization problem, the NP-complete bi-objective minimum spanning tree problem. More specifically, we show that the NSGA-II with population size N ≥ 4((n - 1)wmax + 1) computes all extremal points of the Pareto front in an expected number of O(m2nwmax log(nwmax)) iterations, where n is the number of vertices, m the number of edges, and wmax is the maximum edge weight in the problem instance. This result confirms, via mathematical means, the good performance of the NSGA-II observed empirically. It also paves the way for analyses of the NSGA-II on complex combinatorial optimization *** a side result, we also obtain a new analysis of the performance of the GSEMO algorithm on the bi-objective minimum spanning tree problem, which improves the previous best result by a factor of |F|, the number of points in the convex hull of the Pareto front, a set that can be as large as nwmax. The main reason for this improvement is our observation that both algorithms find the different extremal points in parallel rather than sequentially, as assumed in the previous *** paper for the Hot-off-the-Press track at GECCO 2024 summarizes the work Sacha Cerf, Benjamin Doerr, Benjamin Hebras, Jakob Kahane, and Simon Wietheger. 2023. The first proven performance guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a combinatorial optimization problem. In International Joint Conference on Artificial Intelligence, TJCAI2023. ***, 5522 - 5530 [1]. © 2024 Copyright held by the owner/author(s).

关键词： Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

MosaicSets: Embedding Set Systems into Grid Graphs

arXiv

引用

arXiv 2022年

作者： Rottmann, Peter Wallinger, Markus Bonerath, Annika Gedicke, Sven Nöllenburg, Martin Haunert, Jan-Henrik The Geoinformation Group of the University of Bonn Germany The Algorithms and Complexity Group of the Technical University of Vienna Austria

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews. © 2022, CC BY.

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for book embedding problems

引用

Journal of Graph algorithms and Applications 2020年第4期24卷 603-620页

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria Engineering Department University of Perugia Perugia Italy

A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called Fixed-Order Book Thick-ness, or not fixed, called Book Thickness. Both problems are known to be NP-complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order. © 2020, Brown University. All rights reserved.

关键词： Embeddings

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：