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

Level Planarity Is More Difficult Than We Thought 32

学校读者我要写书评

暂无评论

Level Planarity Is More Difficult Than We Thought

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

作者： Fink, Simon D. Pfretzschner, Matthias Rutter, Ignaz Stumpf, Peter Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Computer Science and Mathematics Universität Passau Germany Charles University Prague Czech Republic

We consider three simple quadratic-time algorithms for Level Planarity and give a level-planar instance that they either falsely classify as negative or for which they output a non-planar drawing. © Simon D. Fink... 详细信息

ISBN: (纸本)9783959773430

关键词： Consensus algorithm

Computing Hive Plots: A Combinatorial Framework

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Nöllenburg, Martin Wallinger, Markus Algorithms and Complexity Group TU Wien Austria

Hive plots are a graph visualization style placing vertices on a set of radial axes emanating from a common center and drawing edges as smooth curves connecting their respective endpoints. In previous work on hive plots, assignment to an axis and vertex positions on each axis were determined based on selected vertex attributes and the order of axes was prespecified. Here, we present a new framework focusing on combinatorial aspects of these drawings to extend the original hive plot idea and optimize visual properties such as the total edge length and the number of edge crossings in the resulting hive plots. Our framework comprises three steps: (1) partition the vertices into multiple groups, each corresponding to an axis of the hive plot;(2) optimize the cyclic axis order to bring more strongly connected groups near each other;(3) optimize the vertex ordering on each axis to minimize edge crossings. Each of the three steps is related to a well-studied, but NP-complete computational problem. We combine and adapt suitable algorithmic approaches, implement them as an instantiation of our framework and show in a case study how it can be applied in a practical setting. Furthermore, we conduct computational experiments to gain further insights regarding algorithmic choices of the framework. The code of the implementation and a prototype web application can be found on OSF1 © 2023, CC BY.

关键词： Optimization

Crossing Minimization in Time Interval Storylines

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Dobler, Alexander Nöllenburg, Martin Stojanovic, Daniel Villedieu, Anaïs Wulms, Jules Algorithms and Complexity Group TU Wien Austria

Storyline visualizations are a popular way of visualizing characters and their interactions over time: Characters are drawn as x-monotone curves and interactions are visualized through close proximity of the corresponding character curves in a vertical strip. Existing methods to generate storylines assume a total ordering of the interactions, although real-world data often do not contain such a total order. Instead, multiple interactions are often grouped into coarser time intervals such as years. We exploit this grouping property by introducing a new model called storylines with time intervals and present two methods to minimize the number of crossings and horizontal space usage. We then evaluate these algorithms on a small benchmark set to show their effectiveness. © 2023, CC BY.

关键词：

MySemCloud: Semantic-aware Word Cloud Editing

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Huber, Michael Nöllenburg, Martin Villedieu, Anaïs The Algorithms and Complexity Group at TU Wien Austria

Word clouds are a popular text visualization technique that summarize an input text by displaying its most important words in a compact image. The traditional layout methods do not take proximity effects between words into account;this has been improved in semantic word clouds, where relative word placement is controlled by edges in a word similarity graph. We introduce MySemCloud, a new human-in-the-loop tool to visualize and edit semantic word clouds. MySemCloud lets users perform computer-assisted local moves of words, which improve or at least retain the semantic quality. To achieve this, we construct a word similarity graph on which a system of forces is applied to generate a compact initial layout with good semantic quality. The force system also allows us to maintain these attributes after each user interaction, as well as preserve the user’s mental map. The tool provides algorithmic support for the editing operations to help the user enhance the semantic quality of the visualization, while adjusting it to their personal preference. We show that MySemCloud provides high user satisfaction as well as permits users to create layouts of higher quality than state-of-the-art semantic word cloud generation tools. © 2023, CC BY.

关键词： Visualization

A Note on the complexity of One-Sided Crossing Minimization of Trees

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Dobler, Alexander Algorithms and Complexity Group TU Wien Austria

In 2011, Harrigan and Healy published a polynomial-time algorithm for one-sided crossing minimization for trees [2]. We point out a counterexample to that algorithm, and show that one-sided crossing minimization is NP... 详细信息

关键词： Polynomial approximation

Lossy Kernelization of Same-Size Clustering 1

学校读者我要写书评

暂无评论

17th International Computer Science Symposium in Russia, CSR 2022

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Purohit, Nidhi Siminov, Kirill Department of Informatics University of Bergen Bergen Norway Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (数字)9783031095740

ISBN: (纸本)9783031095733

In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters, from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem, parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existences of an (exact) kernel of polynomial size and a PTAS. © 2022, Springer Nature Switzerland AG.

关键词： Parameterization

Constrained Planarity in Practice Engineering the Synchronized Planarity Algorithm

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2025年第1期29卷 91-123页

作者： Fink, Simon D. Rutter, Ignaz Technische Universität Wien Algorithms and Complexity Group Austria University of Passau Faculty of Computer Science and Mathematics Germany

In the constrained planarity setting, we ask whether a graph admits a planar drawing that additionally satisfies a given set of constraints. These constraints are often derived from very natural problems;prominent examples are Level Planarity, where vertices have to lie on given horizontal lines indicating a hierarchy, and Clustered Planarity, where we in addition to the graph itself draw the boundaries of clusters which recursively group the vertices in a crossing-free manner. Despite receiving significant amount of attention and substantial theoretical progress on these problems, only very few of the found solutions have been put into practice and evaluated experimentally. In this paper, we describe our implementation of the recent quadratic-time algorithm by Bläsius et al. [8] for solving the problem Synchronized Planarity, which can be seen as a common generalization of several constrained planarity problems, including the aforementioned ones. Our experimental evaluation on an existing benchmark set shows that even our baseline implementation outperforms all competitors by at least an order of magnitude. We systematically investigate the degrees of freedom in the implementation of the Synchronized Planarity algorithm for larger instances and propose several modifications that further improve the performance. Altogether, this allows us to solve instances with up to 100 vertices in milliseconds and instances with up to 100 000 vertices within a few minutes. © 2025, Brown University. All rights reserved.

关键词： Drawing (graphics)

PACE Solver Description: Touiouidth 18

学校读者我要写书评

暂无评论

PACE Solver Description: Touiouidth

18th International Symposium on Parameterized and Exact Computation, IPEC 2023

作者： Berthe, Gaétan Coudert-Osmont, Yoann Dobler, Alexander Morelle, Laure Reinald, Amadeus Rocton, Mathis LIRMM CNRS Université de Montpellier France Université de Lorraine CNRS Inria LORIA France Algorithms and Complexity Group TU Wien Austria

We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++... 详细信息

ISBN: (纸本)9783959773058

关键词： Branch and bound method

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