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

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Agrawal, Akanksha Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Verma, Shaily Indian Institute of Technology Madras India University of California Santa BarbaraCA United States School of Computer Science University of Leeds United Kingdom The Institute of Mathematical Sciences HBNI Chennai India Department of Informatics University of Bergen Norway Algorithm Engineering Group Hasso Plattner Institute Potsdam Germany

ISBN: (纸本)9783959773652

The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time f(k)nO(1), where k is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain Ki,j as a subgraph (a.k.a. Ki,j-free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on Ki,j-free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on Ki,j-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and "representative-family" like sets for Ki,j-free graphs that we use in obtaining our results may have wider algorithmic applications. © Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Shaily Verma.

关键词： Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Upward planarization layout

引用

Journal of Graph algorithms and Applications 2011年第1期15卷 127-155页

作者： Chimani, Markus Gutwenger, Carsten Mutzel, Petra Wong, Hoi-Ming Algorithm Engineering Group Friedrich-Schiller-University Jena Germany Chair for Algorithm Engineering TU Dortmund Germany

Recently, we presented a new practical method for upward crossing mini- mization [8], which clearly outperformed existing approaches for drawing hier- archical graphs in that respect. The outcome of this method is an upward planar representation (UPR), a planarly embedded graph in which crossings are repre- sented by dummy vertices. However, straight-forward approaches for drawing such UPRs lead to quite unsatisfactory results. In this paper, we present a new algorithm for drawing UPRs that greatly improves the layout quality, leading to good hierarchal drawings with few crossings. We analyze its performance on well-known benchmark graphs and compare it with alternative approaches.

关键词： Benchmarking

来源：评论

学校读者我要写书评

暂无评论

Quantum-inspired fluid simulation of two-dimensional turbulence with GPU acceleration

引用

Physical Review Research 2025年第1期7卷 013112-013112页

作者： Leonhard Hölscher Pooja Rao Lukas Müller Johannes Klepsch Andre Luckow Tobias Stollenwerk Frank K. Wilhelm BMW Group 80809 Munich Germany Theoretical Physics Saarland University 66123 Saarbrücken Germany Institute for Quantum Computing Analytics (PGI 12) Forschungszentrum Jülich 52425 Jülich Germany Quantum Algorithm Engineering NVIDIA Santa Clara 95051 California USA Institute of Computer Science Ludwig Maximilian University Munich 80539 Munich Germany

Tensor network algorithms can efficiently simulate complex quantum many-body systems by utilizing knowledge of their structure and entanglement. These methodologies have been adapted recently for solving the Navier-Stokes equations, which describe a spectrum of fluid phenomena, from the aerodynamics of vehicles to weather patterns. Within this quantum-inspired paradigm, velocity is encoded as matrix product states (MPS), effectively harnessing the analogy between interscale correlations of fluid dynamics and entanglement in quantum many-body physics. This particular tensor structure is also called quantics tensor train (QTT). By utilizing NVIDIA's cuQuantum library to perform parallel tensor computations on GPUs, our adaptation speeds up simulations by up to 12.1 times. This allows us to study the algorithm in terms of its applicability, scalability, and performance. By simulating two qualitatively different but commonly encountered 2D flow problems at high Reynolds numbers up to 1×107 using a fourth-order time stepping scheme, we find that the algorithm has a potential advantage over direct numerical simulations in the turbulent regime as the requirements for grid resolution increase drastically. In addition, we derive the scaling χ=O(poly(1/ε)) for the maximum bond dimension χ of MPS representing turbulent flow fields, with an error ε, based on the spectral distribution of turbulent kinetic energy. Our findings motivate further exploration of related quantum algorithms and other tensor network methods.

关键词： Navier Stokes equations

来源：评论

学校读者我要写书评

暂无评论

Analysis of Distributed algorithms on Scale-free Networks 9

Analysis of Distributed Algorithms on Scale-free Networks

引用

9th Ph. D. Retreat of the HPI Research School on Service-oriented Systems engineering

作者： Rothenberger, Ralf Algorithm Engineering Group Hasso-Plattner-Institut Germany

ISBN: (纸本)9783869563459

Processor design has reached the so called "power wall": simply increasing computational power by increasing frequency and power intake of individual processors is not justifiable anymore since the imposed hardware problems outweigh their gain. Instead the trend goes to parallelizing IT systems to gain computational power. These changes in hardware and systems design were also accompanied by a change in algorithm design. Although parallel algorithms and parallel computing have been intensively studied in the 80’s and 90’s, this work was mainly on the PRAM model and for homogenous networks. Our aim is the analysis of distributed processes and algorithms on heterogeneous networks, more precisely, on scale-free networks. For this purpose we proposed and analyzed load balancing on Chung-Lu random graphs as a first specific problem in the context of scale-free networks. At the moment of writing we are extending our results to satisfiability problems with non-uniform variable distributions. © 2016 Universitatsverlag Potsdam. All rights reserved.

关键词： Heterogeneous networks

来源：评论

学校读者我要写书评

暂无评论

Exploring Game-Theoretic Formation of Realistic Networks 17

Exploring Game-Theoretic Formation of Realistic Networks

引用

17th HPI Future SOC Lab 2018

作者： Friedrich, Tobias Lenzner, Pascal Schumann, David Algorithm Engineering Group Hasso Plattner Institute for Digital Engineering Germany

ISBN: (纸本)9783869565477

Many real world networks from different domains share the same structural properties. So far, there only exist models which reproduce these properties via a random process and thus have only limited explanatory power. In contrast to this, we have developed an agent-based game-theoretic model which promises a better explanation of the structure of real world networks. Our new model was validated in computationally demanding large-scale experiments performed on the hardware of the HPI Future SOC Lab. © 2018 Universitatsverlag Potsdam. All rights reserved.

关键词： Random processes

来源：评论

学校读者我要写书评

暂无评论

The satisfiability threshold for non-uniform random 2-SAT 46

The satisfiability threshold for non-uniform random 2-SAT

引用

46th International Colloquium on Automata, Languages, and Programming, ICALP 2019

作者： Friedrich, Tobias Rothenberger, Ralf Algorithm Engineering Group Hasso Plattner Institute University of Potsdam Germany

ISBN: (纸本)9783959771092

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worst-case hardness lies at the core of computational complexity theory, for example in the form of NP-hardness and the (Strong) Exponential Time Hypothesis. In practice however, SAT instances can often be solved efficiently. This contradicting behavior has spawned interest in the average-case analysis of SAT and has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, most theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a non-uniform distribution of the variables, which can result in distributions closer to industrial SAT instances. We study satisfiability thresholds of non-uniform random 2-SAT with n variables and m clauses and with an arbitrary probability distribution (pi)i∈[n] with p1 > p2 >... > pn > 0 over the n variables. We show for p21 = Θ (Pni=1 p2i ) that the asymptotic satisfiability threshold is at m = Θ ((1 − Pn i=1 p2i ) /( p1 · (Pn i=2 p2i )1/2)) and that it is coarse. For p21 = o (Pn i=1 p2i ) we show that there is a sharp satisfiability threshold at m = (Pni=1 p2i )−1. This result generalizes the seminal works by Chvatal and Reed [FOCS 1992] and by Goerdt [JCSS 1996]. © Graham Cormode, Jacques Dark, and Christian Konrad;licensed under Creative Commons License CC-BY

关键词： Probability distributions

来源：评论

学校读者我要写书评

暂无评论

Transitions in Dynamic Point Labeling 12

Transitions in Dynamic Point Labeling

引用

12th International Conference on Geographic Information Science, GIScience 2023

作者： Depian, Thomas Li, Guangping Nöllenburg, Martin Wulms, Jules Algorithms and Complexity Group TU Wien Austria Algorithm Engineering Group TU Dortmund Germany

ISBN: (纸本)9783959772884

The labeling of point features on a map is a well-studied topic. In a static setting, the goal is to find a non-overlapping label placement for (a subset of) point features. In a dynamic setting, the set of point features and their corresponding labels change, and the labeling has to adapt to such changes. To aid the user in tracking these changes, we can use morphs, here called transitions, to indicate how a labeling changes. Such transitions have not gained much attention yet, and we investigate different types of transitions for labelings of points, most notably consecutive transitions and simultaneous transitions. We give (tight) bounds on the number of overlaps that can occur during these transitions. When each label has a (non-negative) weight associated to it, and each overlap imposes a penalty proportional to the weight of the overlapping labels, we show that it is NP-complete to decide whether the penalty during a simultaneous transition has weight at most k. Finally, in a case study, we consider geotagged Twitter data on a map, by labeling points with rectangular labels showing tweets. We developed a prototype implementation to evaluate different transition styles in practice, measuring both number of overlaps and transition duration. © Thomas Depian, Guangping Li, Martin Nöllenburg, and Jules Wulms.

关键词： Information retrieval

来源：评论

学校读者我要写书评

暂无评论

BeatTheBeat music-based procedural content generation in a mobile game

BeatTheBeat music-based procedural content generation in a m...

引用

2012 IEEE International Conference on Computational Intelligence and Games, CIG 2012

作者： Jordan, Annika Scheftelowitsch, Dimitri Lahni, Jan Hartwecker, Jannic Kuchem, Matthias Walter-Huber, Mirko Vortmeier, Nils Delbrügger, Tim Güler, Ümit Vatolkin, Igor Preuss, Mike Computational Intelligence Group Department of Algorithm Engineering TU Dortmund Germany

ISBN: (纸本)9781467311922

We present a multi-player mobile game that employs fully automated music feature extraction to create 'levels' and thereby produce game content procedurally. Starting from a pool of songs (and their features), a self-organizing map is used to organize the music into a hexagonal board so that each field contains a song and one of three minigames which can then be played using the song as background and content provider. The game is completely asynchronous: there are no turns, players can start and stop to play anytime. A preference-learning style experiment investigates whether the user is able to discriminate levels that match the music from randomly chosen ones in order to see if the user gets the connection, but at the same time, the levels do not get too predictable. © 2012 IEEE.

关键词： Self organizing maps

来源：评论

学校读者我要写书评

暂无评论

Tuning optimization algorithms for real-world problems by means of surrogate modeling 10

Tuning optimization algorithms for real-world problems by me...

引用

12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010

作者： Preuss, Mike Rudolph, Günter Wessing, Simon Computational Intelligence Group Department of Algorithm Engineering Technische Universität Dortmund Germany

ISBN: (纸本)9781450300728

The case-specific tuning of parameters of optimization metaheuristics like evolutionary algorithms almost always leads to significant improvements in performance. But if the evaluation of the objective function is computationally expensive, which is typically the case for real-worlds problems, an extensive parameter tuning phase on the original problem is prohibitive. Therefore we have developed another approach: Provided that a (computationally cheap) surrogate model is available that reflects the structural characteristics of the original problem then the parameter tuning can be run on the surrogate problem before using the best parameters thereby identified for the metaheuristic when optimizing the original problem. In this experimental study we aim to assess how many function evaluations on the original problem are necessary to build a surrogate model endowed with the characteristics of the original problem and to develop a methodology that measures to which extent such a matching has been achieved. Copyright 2010 ACM.

关键词： Evolutionary algorithms

来源：评论

学校读者我要写书评

暂无评论

Measuring multimodal optimization solution sets with a view to multiobjective techniques

Measuring multimodal optimization solution sets with a view ...

引用

International Conference on EVOLVE

作者： Preuss, Mike Wessing, Simon Computational Intelligence Group Chair of Algorithm Engineering Department of Computer Science TU Dortmund Dortmund Germany

ISBN: (纸本)9783319011271

As in multiobjective optimization, multimodal optimization generates solution sets that must be measured in order to compare different optimization algorithms. We discuss similarities and differences in the requirements for measures in both domains and suggest a property-based taxonomy. The process of measuring actually consists of two subsequent steps, a subset selection that only considers 'suitable' points (or just takes all available points of a solution set) and the actual measuring. Known quality indicators often rely on problem knowledge (objective values and/or locations of optima and basins) which makes them unsuitable for real-world applications. Hence, we propose a new subset selection heuristic without such demands, which thereby enables measuring solution sets of single-objective problems, provided a distance metric exists.

关键词： Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：