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

Drawing Large Graphs by Multilevel Maxent-Stress Optimization

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2018年第5期24卷 1814-1827页

作者： Meyerhenke, Henning Noellenburg, Martin Schulz, Christian KIT Inst Theoret Informat D-76131 Karlsruhe Germany TU Wien Algorithms & Complex Grp A-1040 Vienna Austria Univ Vienna Dept Comp Sci A-1010 Vienna Austria Karlsruhe Inst Technol D-76131 Karlsruhe Germany

Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. Here we present a novel multilevel algorithm to compute a graph layout with respect to the maxent-stress metric proposed by Gansner et al. (2013) that combines layout stress and entropy. As opposed to previous work, we do not solve the resulting linear systems of the maxent-stress metric with a typical numerical solver. Instead we use a simple local iterative scheme within a multilevel approach. To accelerate local optimization, we approximate long-range forces and use shared-memory parallelism. Our experiments validate the high potential of our approach, which is particularly appealing for dynamic graphs. In comparison to the previously best maxent-stress optimizer, which is sequential, our parallel implementation is on average 30 times faster already for static graphs (and still faster if executed on a single thread) while producing a comparable solution quality.

关键词： Graph layout algorithm engineering multilevel algorithm

来源：评论

学校读者我要写书评

暂无评论

Facets for Art Gallery Problems

引用

algorithmICA 2015年第2期73卷 411-440页

作者： Fekete, Sandor P. Friedrichs, Stephan Kroeller, Alexander Schmidt, Christiane Tech Univ Carolo Wilhelmina Braunschweig Inst Betriebssyst & Rechnerverbund D-38106 Braunschweig Germany

The Art Gallery Problem (AGP) asks for placing a minimum number of stationary guards in a polygonal region , such that all points in are guarded. The problem is known to be NP-hard, and its inherent continuous structure (with both the set of points that need to be guarded and the set of points that can be used for guarding being uncountably infinite) makes it difficult to apply a straightforward formulation as an integer linear program. We use an iterative primal-dual relaxation approach for solving AGP instances to optimality. At each stage, a pair of LP relaxations for a finite candidate subset of primal covering and dual packing constraints and variables is considered;these correspond to possible guard positions and points that are to be guarded. Particularly useful are cutting planes for eliminating fractional solutions. We identify two classes of facets, based on Edge Cover and Set Cover (SC) inequalities. Solving the separation problem for the latter is NP-complete, but exploiting the underlying geometric structure, we show that large subclasses of fractional SC solutions cannot occur for the AGP. This allows us to separate the relevant subset of facets in polynomial time. We also characterize all facets for finite AGP relaxations with coefficients in . Finally, we demonstrate the practical usefulness of our approach. Our cutting plane technique yields a significant improvement in terms of speed and solution quality due to considerably reduced integrality gaps as compared to the approach by Kroller et al. (ACM J Exp algorithm 17(1): 2.3:2.1-2.3:2.23, 2012).

关键词： Art gallery problem Geometric optimization algorithm engineering Solving NP-hard problem instances to optimality Art gallery polytope Set cover polytope Facets Cutting planes

来源：评论

学校读者我要写书评

暂无评论

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

引用

algorithmICA 2015年第3期71卷 636-660页

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

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

来源：评论

学校读者我要写书评

暂无评论

Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs

引用

DISCRETE APPLIED MATHEMATICS 2005年第2期145卷 219-231页

作者： Alber, J Dorn, F Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

Many NP-complete problems on planar graphs are "fixed-parameter tractable:" Recent theoretical work provided tree decomposition-based fixed-parameter algorithms exactly solving various parameterized problems on planar graphs, among others VERTEX COVER, in time O(c(rootk)n). Here, c is some constant depending on the graph problem to be solved, n is the number of graph vertices, and k is the problem parameter (for VERTEX COVER this is the size of the vertex cover). In this paper, we present an experimental study for such tree decomposition-based algorithms focusing on VERTEX COVER. We demonstrate that the tree decomposition-based approach provides a valuable way of exactly solving VERTEX COVER on planar graphs. Doing so, we also demonstrate the impressive power of the so-called Nemhauser/Trotter theorem which provides a VERTEX COVER-specific, extremely useful data reduction through polynomial time preprocessing. Altogether, this underpins the practical importance of the underlying theory. (C) 2004 Elsevier B.V. All rights reserved.

关键词： algorithm engineering fixed-parameter tractability Vertex Cover tree decomposition of graphs planar graphs exact algorihms

来源：评论

学校读者我要写书评

暂无评论

algorithms for the workflow satisfiability problem engineered for counting constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期32卷 3-24页

作者： Cohen, D. Crampton, J. Gagarin, A. Gutin, G. Jones, M. Royal Holloway Univ London Egham TW20 0EX Surrey England

The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification that satisfies the constraints in the specification. The problem is NP-hard in general, but several subclasses of the problem are known to be fixed-parameter tractable (FPT) when parameterized by the number of steps in the specification. In this paper, we consider the WSP with user-independent counting constraints, a large class of constraints for which the WSP is known to be FPT. We describe an efficient implementation of an FPT algorithm for solving this subclass of the WSP and an experimental evaluation of this algorithm. The algorithm iteratively generates all equivalence classes of possible partial solutions until, whenever possible, it finds a complete solution to the problem. We also provide a reduction from a WSP instance to a pseudo-Boolean (PB) SAT instance. We apply this reduction to the instances used in our experiments and solve the resulting PB SAT problems using SAT4J, a PB SAT solver. We compare the performance of our algorithm with that of SAT4J and discuss which of the two approaches would be more effective in practice.

关键词： Workflow satisfiability problem (WSP) Fixed-parameter tractability (FPT) algorithm engineering Reduction to the pseudo-Boolean SAT problem User-independent constraints

来源：评论

学校读者我要写书评

暂无评论

Designing and implementing algorithms for the closest string problem

引用

THEORETICAL COMPUTER SCIENCE 2019年 786卷 32-43页

作者： Yuasa, Shota Chen, Zhi-Zhong Ma, Bin Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan Univ Waterloo Sch Comp Sci 200 Univ Ave W Waterloo ON N2L 3G1 Canada City Univ Hong Kong Dept Comp Sci Kowloon Tat Chee Ave Hong Kong Peoples R China City Univ Hong Kong Shenzhen Res Inst Shenzhen Hitech Ind Pk Shenzhen Peoples R China

Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string t(sol) that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in O (n(2)L + n(2)d. 6.16(d)) time, while the previously best deterministic algorithm runs in O (nL + nd(3). 6.731(d)) time. (C) 2018 Elsevier B.V. All rights reserved.

关键词： The closest string problem Fixed-parameter algorithms Computational biology algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Exact Routing in Large Road Networks Using Contraction Hierarchies

引用

TRANSPORTATION SCIENCE 2012年第3期46卷 388-404页

作者： Geisberger, Robert Sanders, Peter Schultes, Dominik Vetter, Christian Karlsruhe Inst Technol Dept Informat D-76128 Karlsruhe Germany

Contraction hierarchies are a simple approach for fast routing in road networks. Our algorithm calculates exact shortest paths and handles road networks of whole continents. During a preprocessing step, we exploit the inherent hierarchical structure of road networks by adding shortcut edges. A subsequent modified bidirectional Dijkstra algorithm can then find a shortest path in a fraction of a millisecond, visiting only a few hundred nodes. This small search space makes it suitable to implement it on a mobile device. We present a mobile implementation that also handles changes in the road network, like traffic jams, and that allows instantaneous routing without noticeable delay for the user. Also, an algorithm to calculate large distance tables is currently the fastest if based on contraction hierarchies.

关键词： route planning shortest paths algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Collision-free allocation of temporally constrained tasks in multi-robot systems

引用

ROBOTICS AND AUTONOMOUS SYSTEMS 2019年 119卷 151-172页

作者： D'Emidio, Mattia Khan, Imran Univ LAquila Dept Comp Sci Informat Engn & Math DISIM Via Vetoio I-67100 Laquila Italy Gran Sasso Sci Inst Via F Crispi I-67100 Laquila Italy

Multi-robot systems (mRs) are a reference solution for many prominent real-world applications, e.g. management of warehouses or exploration of unknown environments. One of the most fundamental computational problems in MRS is that of planning the assignment of tasks to robots when such tasks have deadlines, i.e. constraints on when the execution must take place. The problem, when multiple objective functions of interest need to be optimized, is both NP-Hard and hard to approximate, and few heuristics are known in the literature to handle it. Unfortunately, none of them guarantees that the trajectories used by the robots when moving between tasks' locations are collision-free at planning time. Rather, they implement a reactive behavior, i.e. they abort the execution of a planned task whenever something goes wrong, e.g. trajectories of robots intersect or a deadline is missed due to some obstacle. This approach induces negative effects on the global performance of the system in the form of waste of energy, due to high distances traveled by the fleet members, or in the form of high convergence time to execute tasks. Therefore, planning the assignments of temporally constrained tasks with the guarantee of avoiding collisions can be a desirable feature for multi-robot systems. In this paper, we present CFAT-D (Collision-Free Allocation of Tasks having Deadlines), a new algorithm that can allocate temporally constrained tasks while guaranteeing that used trajectories are collision-free at planning time. We prove CFAT-D to be correct and showcase its effectiveness through an extensive experimental evaluation. Finally, we provide a roadmap toward the practical implementation of the new strategy in real-world environments. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Multi-robot systems Distributed algorithms Task allocation Path planning algorithm engineering Scheduling

来源：评论

学校读者我要写书评

暂无评论

Automated generation of search tree algorithms for hard graph modification problems

引用

algorithmICA 2004年第4期39卷 321-347页

作者： Gramm, J Guo, J Hüffner, F Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

We present a framework for an automated generation of exact search tree algorithms for NP-hard problems. The purpose of our approach is twofold-rapid development and improved upper bounds. Many search tree algorithms for various problems in the literature are based on complicated case distinctions. Our approach may lead to a much simpler process of developing and analyzing these algorithms. Moreover, using the sheer computing power of machines it may also lead to improved upper bounds on search tree sizes (i.e., faster exact solving algorithms) in comparison with previously developed "hand-made" search trees. Among others, such an example is given with the NP-complete Cluster Editing problem (also known as Correlation Clustering on complete unweighted graphs), which asks for the minimum number of edge additions and deletions to create a graph which is a disjoint union of cliques. The hand-made search tree for Cluster Editing had worst-case size O(2.27(k)), which now is improved to O(1.92(k)) due to our new method. (Herein, k denotes the number of edge modifications allowed.).

关键词： NP-hard problems graph modification search tree algorithms exact algorithms automated development and analysis of algorithms algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Separator-based data reduction for signed graph balancing

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第4期20卷 335-360页

作者： Hueffner, Falk Betzler, Nadja Niedermeier, Rolf Univ Jena Inst Informat D-07743 Jena Germany

Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.

关键词： Preprocessing Exact algorithm Parameterized algorithmics algorithm engineering Gene-regulatory network Financial network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：