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

Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs

10th Workshop on algorithm engineering and Experiments/5th Workshop on Analytic algorithmics and Combinatorics

作者： Bian, Zhengbing Gu, Qian-Ping Marzban, Marjan Tamaki, Hisao Yoshitake, Yumi Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Meiji Univ Dept Comp Sci Kawasaki Kanagawa 2148571 Japan

ISBN: (纸本)9780898716535

We propose efficient implementations of Seymour and Thomas algorithm which, given a planar graph and an integer beta, decides whether the graph has the branchwidth at least beta. The computational results of our implementations show that the branchwidth of a planar graph can be computed in a practical time and memory space for some instances of size about one hundred thousand edges. Previous studies report that a straightforward implementation of the algorithm is memory consuming, which could be a bottleneck for solving instances with more than a few thousands edges. Our results suggest that with efficient implementations, the memory space required by the algorithm may not be a bottleneck in practice. Applying our implementations, an optimal branch decomposition of a planar graph of practical size can be computed in a reasonable time. Branch-decomposition based algorithms have been explored as an approach for solving many NP-hard problems on graphs. The results of this paper suggest that the approach could be practical.

关键词： Graph algorithms branch-decomposition planar graphs algorithm engineering computational study

来源：评论

学校读者我要写书评

暂无评论

Multimodal Route and Tour Planning in Urban Environments

Multimodal Route and Tour Planning in Urban Environments

引用

IEEE Symposium on Computers and Communications (ISCC)

作者： Dibbelt, Julian Gavalas, Damianos Kasapakis, Vlasios Konstantopoulos, Charalampos Kontogiannis, Spyros Pantziou, Grammati Wagner, Dorothea Zaroliagis, Christos Karlsruhe Inst Technol Karlsruhe Germany Univ Aegean Dept Prod & Syst Design Engn Syros Greece CTI Patras Greece Univ Aegean Dept Cultural Technol & Commun Mitilini Greece Univ Piraeus Dept Informat Piraeus Greece Univ Ioannina Dept Comp Sci Engn Ioannina Greece Technol Educ Inst Athens Dept Informat Athens Greece Univ Patras Dept Comp Engn & Informat Patras Greece

ISBN: (纸本)9781538616291

The environmental impact of the steadily increasing demand for mobility of people and goods, especially in urban environments, raises public concern and presents challenges that need to be addressed in the interest of long-term sustainability. Along this line, the inherently eco-friendly human mobility which involves the use of urban public transit networks must be encouraged and eased. This necessitates the development of context-aware services that hide the complexity of public transit networks while considering all available transportation modalities (e.g. bus, metro, tram, walking and cycling) in order to provide sophisticated route planning tailored to both residents and visitors of urban areas. The EU-funded eCOMPASS research project has addressed this challenge through establishing a methodological framework for route planning optimization. A core objective of the project has been to employ novel algorithm engineering approaches for delivering a comprehensive set of tools and services (accessible from web/mobile application interfaces) for mobile end users to enable eco-awareness in urban multi-modal transfers. eCOMPASS delivered web and mobile services providing multimodal public transportation route planning, considering contextual information as well as various restrictions and/or user constraints. Herein, we report the motivation, main scientific innovations and present the end-products of eCOMPASS with respect to multimodal human mobility.

关键词： Multimodal route planning tourist tour planning algorithm engineering combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Speeding Up Dynamic Programming with Representative Sets: An Experimental Evaluation of algorithms for Steiner Tree on Tree Decompositions

Speeding Up Dynamic Programming with Representative Sets: An...

引用

8th International Symposium on Parameterized and Exact Computation (IPEC) as part of the annual ALGO Meeting

作者： Fafianie, Stefan Bodlaender, Hans L. Nederlof, Jesper Univ Utrecht Utrecht Netherlands

ISBN: (纸本)9783319038971

Dynamic programming on tree decompositions is a frequently used approach to solve otherwise intractable problems on instances of small treewidth. In recent work by Bodlaender et al. (Proceedings of the 40th international colloquium on automata, languages and programming, ICALP 2013, part I, volume 7965 of Lecture Notes in Computer Science. Springer, Berlin, pp 196-207, 2013), it was shown that for many connectivity problems, there exist algorithms that use time linear in the number of vertices and single exponential in the width of the tree decomposition that is used. The central idea is that it suffices to compute representative sets, and that these can be computed efficiently with help of Gaussian elimination. In this paper, we give an experimental evaluation of this technique for the Steiner Tree problem. Our comparison of the classic dynamic programming algorithm and the improved dynamic programming algorithm that employs table reduction shows that the new approach gives significant improvements on the running time of the algorithm and the size of the tables computed by the dynamic programming algorithm. Thus, the rank-based approach from Bodlaender et al. (2013) does not only give significant theoretical improvements but also is a viable approach in a practical setting, and showcases the potential of exploiting the idea of representative sets for speeding up dynamic programming algorithms. Furthermore, we propose an alternative representation of partial solutions using weighted bit strings in order to circumvent a part of the reduction step that is computationally expensive in practice. In the experimental evaluation we find that this representation yields further significant improvements. We show that the representation can also be used for the other problems fitting in the framework of Bodlaender et al. (2013).

关键词： Experimental evaluation algorithm engineering Steiner tree Treewidth Dynamic programming Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Equivalence Between Stochastic Tournament and Power-Law Ranking Selection and How to Implement Them Efficiently 18th

On the Equivalence Between Stochastic Tournament and Power-L...

引用

18th International Conference on Parallel Problem Solving from Nature (PPSN)

作者： Duc-Cuong Dang Opris, Andre Sudholt, Dirk Univ Passau Passau Germany

ISBN: (纸本)9783031700705;9783031700712

Tournament selection is a popular parent selection mechanism in evolutionary algorithms. Bian and Qian (PPSN 2022) proved that choosing the tournament size uniformly at random, called stochastic tournament selection, in combination with crossover significantly improves the performance of NSGA-II on some benchmark functions. We show that this selection mechanism is asymptotically equivalent to the power-law ranking selection proposed in Covantes Osuna et al. (Theor. Comput. Sci. 832, 2020) with the exponent of 2. Thus asymptotic runtime bounds proven for one operator also hold when one operator is replaced with the other. We also investigate how to implement these operators efficiently for NSGA-II on the problems considered in the previous papers. We propose to implement the stochastic tournament with a pre-computed selection distribution to save on random numbers. Experiments on high dimensional problems demonstrate the superiority of this method compared to the standard implementation. Overall, the power-law ranking selection is the most efficient selection mechanism for the studied problems. Remarkably, we also find that the way ties are broken between equally fit solutions can make the difference between the best and the worst approach, especially when crossover is involved.

关键词： Selection operators tournament selection power-law ranking multi-objective optimisation runtime analysis algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Distributed Time-Dependent Contraction Hierarchies

Distributed Time-Dependent Contraction Hierarchies

引用

9th International Symposium on Experimental algorithms

作者： Kieritz, Tim Luxen, Dennis Sanders, Peter Vetter, Christian Karlsruher Inst Technol Karlsruhe Germany

ISBN: (纸本)9783642131929

Server based route planning in road networks is now powerful enough to find quickest paths in a matter of milliseconds, even if detailed information on time-dependent travel times is taken into account. However this requires huge amounts of memory on each query server and hours of preprocessing even for a medium sized country like Germany. This is a problem since global internet companies would like to work with transcontinental networks, detailed models of intersections, and regular re-preprocessing that takes the current traffic situation into account. By giving a distributed memory parallelization of the arguably best current technique - time-dependent contraction hierarchies, we remove these bottlenecks. For example, on a medium size network 64 processes accelerate preprocessing by a factor of 28 to 160 seconds, reduce per process memory consumption by a factor of 10.5 and increase query throughput by a factor of 25.

关键词： time-dependent shortest paths distributed computation message passing algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Parallel algorithms Reconsidered 32

Parallel Algorithms Reconsidered

引用

32nd International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Sanders, Peter Karlsruhe Inst Technol Karlsruhe Germany

ISBN: (纸本)9783939897781

Parallel algorithms have been a subject of intensive algorithmic research in the 1980s. This research almost died out in the mid 1990s. In this paper we argue that it is high time to reconsider this subject since a lot of things have changed. First and foremost, parallel processing has moved from a niche application to something mandatory for any performance critical computer applications. We will also point out that even very fundamental results can still be obtained. We give examples and also formulate some open problems.

关键词： parallel algorithm algorithm engineering communication efficient algorithm polylogarithmic time algorithm parallel machine model

来源：评论

学校读者我要写书评

暂无评论

Renewable Mobility in Smart Cities: Cloud-Based Services

Renewable Mobility in Smart Cities: Cloud-Based Services

引用

IEEE Symposium on Computers and Communications (IEEE ISCC)

作者： Gavalas, Damianos Giannakopoulou, Kalliopi Kasapakis, Vlasios Kehagias, Dionisis Konstantopoulos, Charalampos Kontogiannis, Spyros Kypriadis, Damianos Pantziou, Grammati Paraskevopoulos, Andreas Zaroliagis, Christos Univ Aegean Dept Prod & Syst Design Engn Syros Greece CTI Patras Greece Univ Patras Dept Comp Engn & Informat Patras Greece Univ Aegean Dept Cultural Technol & Commun Mitilini Greece Ctr Res & Technol Hellas Informat Technol Inst CERTH ITI Thessaloniki Greece Univ Piraeus Dept Informat Piraeus Greece Univ Ioannina Dept Comp Sci & Engn Ioannina Greece Technol Educ Inst Athens Dept Informat Athens Greece

ISBN: (纸本)9781538669501

Providing efficient, sustainable and personalized mobility services in urban environments that combine a spectrum of transport modes (e.g., public transport, electric vehicles, vehicle sharing, low energy and/or emission routes) constitutes a great challenge. In this work, we present MOVESMART, a holistic approach (and integrated platform) for the provision of renewable personal mobility services, leveraging crowd-sourcing data, tools for collecting real-time information by multimodal travelers, and traffic prediction mechanisms. MOVESMART guarantees real-time responses to renewable (on-demand) mobility queries for efficient multi-modal route planning that are time-dependent as well as sensitive to aperiodic incidents and traffic prediction forecasts. This paper focuses on the cloud-based (backend) services of the MOVESMART platform.

关键词： Sustainable mobility renewable mobility multimodal route planning crowdsourcing vehicle sharing algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Stronger ILPs for the Graph Genus Problem 27

Stronger ILPs for the Graph Genus Problem

引用

27th Annual European Symposium on algorithms (ESA)

作者： Chimani, Markus Wiedera, Tilo Osnabruck Univ Theoret Comp Sci Osnabruck Germany

ISBN: (纸本)9783959771245

The minimum genus of a graph is an important question in graph theory and a key ingredient in several graph algorithms. However, its computation is NP-hard and turns out to be hard even in practice. Only recently, the first non-trivial approach - based on SAT and ILP (integer linear programming) models - has been presented, but it is unable to successfully tackle graphs of genus larger than 1 in practice. Herein, we show how to improve the ILP formulation. The crucial ingredients are two-fold. First, we show that instead of modeling rotation schemes explicitly, it suffices to optimize over partitions of the (bidirected) arc set A of the graph. Second, we exploit the cycle structure of the graph, explicitly mapping short closed walks on A to faces in the embedding. Besides the theoretical advantages of our models, we show their practical strength by a thorough experimental evaluation. Contrary to the previous approach, we are able to quickly solve many instances of genus > 1.

关键词： algorithm engineering genus integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Developing a Multiple-Objective Demand Response algorithm for the Residential Context 21st

Developing a Multiple-Objective Demand Response Algorithm fo...

引用

21st International Conference on Business Information Systems (BIS)

作者： Behrens, Dennis Schoormann, Thorsten Knackstedt, Ralf Univ Hildesheim Dept Informat Syst Univ Pl 1 D-31141 Hildesheim Germany

ISBN: (纸本)9783319939315;9783319939308

Energy grids are facing various challenges, such as new appliances and volatile generation. As grid reliability and cost benefits are endangered, managing appliances becomes increasingly important. Demand Response (DR) is one possibility to contribute to this task by shifting and managing electrical loads. DR can address multiple objectives. However, current research lacks of algorithms addressing these objectives sufficiently. Thus, we aim to develop a DR algorithm that considers multiple DR objectives. For evaluation, we implemented the algorithm and formulated demonstration cases for a simulation. The evaluated algorithm contributes for example to users and energy providers by realizing various benefits.

关键词： Demand Response Demand side management algorithm engineering Greedy heuristic Optimization

来源：评论

学校读者我要写书评

暂无评论

On Design and Implementation of a Generic Number Type for Real Algebraic Number Computations Based on Expression Dags

引用

MATHEMATICS IN COMPUTER SCIENCE 2010年第4期4卷 539-556页

作者： Moerig, Marc Roessling, Ivo Schirra, Stefan Univ Magdeburg Fac Comp Sci Dept Simulat & Graph Univ Pl 2 D-39106 Magdeburg Germany

We report on the design and implementation of a number type called Real_algebraic. This number type allows us to compute the sign of arithmetic expressions involving the operations +,-, ., /, d root. The sign computation is always correct and, in this sense, not subject to rounding errors. We focus on modularity and use generic programming techniques to make key parts of the implementation exchangeable. Thus, our design allows for easily performing experiments with different implementations or thereby tailoring the number type for specific tasks. For many problems in computational geometry, instantiations of our number type Real_algebraic are a user-friendly alternative for implementing the exact geometric computation paradigm in order to abandon numerical robustness problems.

关键词： Symbolic numeric computation Exact geometric computation algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：