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

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

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

Parameterised Partially-Predrawn Crossing Number 38

学校读者我要写书评

暂无评论

Parameterised Partially-Predrawn Crossing Number

38th International Symposium on Computational Geometry, SoCG 2022

作者： Hamm, Thekla Hlinený, Petr Algorithms and Complexity Group TU Wien Austria Faculty of Informatics Masaryk University Brno Czech Republic

ISBN: (纸本)9783959772273

Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph parameter, the crossing number. Specifically, we define the partially predrawn crossing number to be the smallest number of crossings in any drawing of a graph, part of which is prescribed on the input (not counting the prescribed crossings). Our main result - an FPT-algorithm to compute the partially predrawn crossing number - combines advanced ideas from research on the classical crossing number and so called partial planarity in a very natural but intricate way. Not only do our techniques generalise the known FPT-algorithm by Grohe for computing the standard crossing number, they also allow us to substantially improve a number of recent parameterised results for various drawing extension problems. © Thekla Hamm and Petr Hlinn;licensed under Creative Commons License CC-BY 4.0

关键词： Parameterization

Co-Certificate Learning with SAT Modulo Symmetries

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Kirchweger, Markus Peitl, Tomáš Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

We present a new SAT-based method for generating all graphs up to isomorphism that satisfy a given co-NP property. Our method extends the SAT Modulo Symmetry (SMS) framework with a technique that we call co-certificate learning. If SMS generates a candidate graph that violates the given co-NP property, we obtain a certificate for this violation, i.e., ‘co-certificate’ for the co-NP property. The co-certificate gives rise to a clause that the SAT solver, serving as SMS’s backend, learns as part of its CDCL procedure. We demonstrate that SMS plus co-certificate learning is a powerful method that allows us to improve the best-known lower bound on the size of Kochen-Specker vector systems, a problem that is central to the foundations of quantum mechanics and has been studied for over half a century. Our approach is orders of magnitude faster and scales significantly better than a recently proposed SAT-based method. Copyright © 2023, The Authors. All rights reserved.

关键词： Quantum theory