Search

Temporal trees are trees that evolve over a discrete set of time steps. Each time step is associated with a node‐weighted rooted tree and consecutive trees change by adding new nodes, removing nodes, splitting nodes, merging nodes, and changing node weights. Recently, two‐dimensional visualizations of temporal trees called temporal treemaps have been proposed, representing the temporal dimension on the x‐axis, and visualizing the tree modifications over time as temporal edges of varying thickness. The tree hierarchy at each time step is depicted as a vertical, one‐dimensional nesting relationships, similarly to standard, non‐temporal treemaps. Naturally, temporal edges can cross in the visualization, decreasing readability. Heuristics were proposed to minimize such crossings in the literature, but a formal characterization and minimization of crossings in temporal treemaps was left open. In this paper, we propose two variants of defining crossings in temporal treemaps that can be combinatorially characterized. For each variant, we propose an exact optimization algorithm based on integer linear programming and heuristics based on graph drawing techniques. In an extensive experimental evaluation, we show that on the one hand the exact algorithms reduce the number of crossings by a factor of 20 on average compared to the previous algorithms. On the other hand, our new heuristics are faster by a factor of more than 100 and still reduce the number of crossings by a factor of almost three. [ABSTRACT FROM AUTHOR]

The introduction of 5G technologies has enabled the possibility of designing and building several new classes of networked information systems that were previously impossible to implement due to limitations on data throughput or the reliability of transmission channels. Among them, one of the most interesting and successful examples with a highly positive impact in terms of the quality of urban environments and societal and economical welfare is a system of semi-autonomous connected vehicles, where IoT devices, data centers, and fleets of smart vehicles equipped with communication and computational resources are combined into a heterogeneous and distributed infrastructure, unifying hardware, networks, and software. In order to efficiently provide various services (e.g., patrolling, pickup and delivery, monitoring), these systems typically rely on collecting and broadcasting large amounts of data (e.g., sensor data, GPS traces, or maps), which need to be properly collected and processed in a timely manner. As is well documented in the literature, one of the most effective ways to achieve this purpose, especially in a real-time context, is to adopt a graph model of the data (e.g., to model communication networks, roads, or interactions between vehicles) and to employ suitable graph algorithms to solve properly defined computational problems of interest (e.g., shortest paths or distributed consensus). While research in this context has been extensive from a theoretical perspective, works that have focused on the implementation, deployment, and evaluation of the practical performance of graph algorithms for real-world systems of autonomous vehicles have been much rarer. In this paper, we present a study of this kind. Specifically, we first describe the main features of a real-world information system employing semi-autonomous connected vehicles that is currently being tested in the city of L'Aquila (Italy). Then, we present an overview of the computational challenges arising in the considered application domain and provide a systematic survey of known algorithmic results for one of the most relevant classes of computational problems that have to be addressed in said domain, namely, pickup and delivery problems. Finally, we discuss implementation issues, adopted software tools, and the deployment and testing phases concerning one of the algorithmic components of the mentioned real-world system dedicated to handling a specific problem of the above class, namely, the pickup and delivery multi-vehicle problem with time windows. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a directed and weighted graph with a vertex set V of size n and an edge set E of size m such that each edge (u , v) ∈ E has a real-valued weight w (u , c) . An arborescence in G is a subgraph T = (V , E ′) such that, for a vertex u ∈ V , which is the root, there is a unique path in T from u to any other vertex v ∈ V . The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with a minimum weight, i.e., an optimal arborescence. Furthermore, when G is subject to changes, namely, edge insertions and deletions, we are interested in efficiently maintaining a dynamic arborescence in G. This is a well-known problem with applications in several domains such as network design optimization and phylogenetic inference. In this paper, we revisit the algorithmic ideas proposed by several authors for this problem. We provide detailed pseudocode, as well as implementation details, and we present experimental results regarding large scale-free networks and phylogenetic inference. Our implementation is publicly available. [ABSTRACT FROM AUTHOR]

We give an overview of the 2022 Computational Geometry Challenge targeting the problem Minimum Partition into Plane Subsets, which consists of partitioning a given set of line segments into a minimum number of non-crossing subsets. [ABSTRACT FROM AUTHOR]

We study a multimodal journey planning scenario consisting of a public transit network and a transfer graph that represents a secondary transportation mode (e.g., walking, cycling, e-scooter). The objective is to compute Pareto-optimal journeys with respect to arrival time and the number of used public transit trips. Whereas various existing algorithms can efficiently compute optimal journeys in either a pure public transit network or a pure transfer graph, combining the two increases running times significantly. Existing approaches, therefore, typically only support limited walking between stops by either imposing a maximum transfer distance or requiring the transfer graph to be transitively closed. To overcome these shortcomings, we propose a novel preprocessing technique called unlimited transfers (ULTRA): given an unlimited transfer graph, which may represent any non–schedule based transportation mode, ULTRA computes a small number of transfer shortcuts that are provably sufficient for computing a Pareto set of optimal journeys. These transfer shortcuts can be integrated into a variety of state-of-the-art public transit algorithms, establishing the ULTRA-query algorithm family. Our extensive experimental evaluation shows that ULTRA improves these algorithms from limited to unlimited transfers without sacrificing query speed. This is true not just for walking, but also for faster transfer modes, such as bicycle or car. Compared with the state of the art for multimodal journey planning, the fastest ULTRA-based algorithm achieves a speedup of an order of magnitude. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant WA 654/23-2]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0198. [ABSTRACT FROM AUTHOR]

Fast extraction of top- $k$ distances from graph data is a primitive of paramount importance in the fields of data mining, network analytics and machine learning, where ranked distances are exploited for several purposes (e.g., link prediction or network classification). While investigation on computational methods to address this retrieval task for regularly sized, static inputs has been extensive, much less is known when managed graphs are massive, i.e., having millions of vertices/edges, and time-evolving, i.e., when their structure can grow over time, a scenario that introduces a number of scalability and effectiveness issues otherwise not arising. Since, nowadays, most real-world applications exploiting top- $k$ distances have to handle inherently dynamic and rapidly growing graphs, in this paper we present the first dynamic indexing scheme that supports very fast queries on top- $k$ distances when graphs are massive and incrementally time-evolving. We assess the scalability and effectiveness of our method through extensive experimentation on both real-world and artificial graph datasets.

The introduction of 5G technologies has enabled the possibility of designing and building several new classes of networked information systems that were previously impossible to implement due to limitations on data throughput or the reliability of transmission channels. Among them, one of the most interesting and successful examples with a highly positive impact in terms of the quality of urban environments and societal and economical welfare is a system of semi-autonomous connected vehicles, where IoT devices, data centers, and fleets of smart vehicles equipped with communication and computational resources are combined into a heterogeneous and distributed infrastructure, unifying hardware, networks, and software. In order to efficiently provide various services (e.g., patrolling, pickup and delivery, monitoring), these systems typically rely on collecting and broadcasting large amounts of data (e.g., sensor data, GPS traces, or maps), which need to be properly collected and processed in a timely manner. As is well documented in the literature, one of the most effective ways to achieve this purpose, especially in a real-time context, is to adopt a graph model of the data (e.g., to model communication networks, roads, or interactions between vehicles) and to employ suitable graph algorithms to solve properly defined computational problems of interest (e.g., shortest paths or distributed consensus). While research in this context has been extensive from a theoretical perspective, works that have focused on the implementation, deployment, and evaluation of the practical performance of graph algorithms for real-world systems of autonomous vehicles have been much rarer. In this paper, we present a study of this kind. Specifically, we first describe the main features of a real-world information system employing semi-autonomous connected vehicles that is currently being tested in the city of L’Aquila (Italy). Then, we present an overview of the computational challenges arising in the considered application domain and provide a systematic survey of known algorithmic results for one of the most relevant classes of computational problems that have to be addressed in said domain, namely, pickup and delivery problems. Finally, we discuss implementation issues, adopted software tools, and the deployment and testing phases concerning one of the algorithmic components of the mentioned real-world system dedicated to handling a specific problem of the above class, namely, the pickup and delivery multi-vehicle problem with time windows.

Let G=(V,E) be a directed and weighted graph with a vertex set V of size n and an edge set E of size m such that each edge (u,v)∈E has a real-valued weight w(u,c). An arborescence in G is a subgraph T=(V,E′) such that, for a vertex u∈V, which is the root, there is a unique path in T from u to any other vertex v∈V. The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with a minimum weight, i.e., an optimal arborescence. Furthermore, when G is subject to changes, namely, edge insertions and deletions, we are interested in efficiently maintaining a dynamic arborescence in G. This is a well-known problem with applications in several domains such as network design optimization and phylogenetic inference. In this paper, we revisit the algorithmic ideas proposed by several authors for this problem. We provide detailed pseudocode, as well as implementation details, and we present experimental results regarding large scale-free networks and phylogenetic inference. Our implementation is publicly available.

We give an overview of the 2021 Computational Geometry Challenge, which targeted the problem of optimally coordinating a set of robots by computing a family of collision-free trajectories for a set S of n pixel-shaped objects from a given start configuration to a desired target configuration. [ABSTRACT FROM AUTHOR]

The third computational geometry challenge was on a coordinated path planning problem in which a collection of square robots need to move on the integer grid, from their given starting points to their target points, and without collision between robots, or between robots and a set of input obstacles. We designed and implemented three algorithms for this problem. First, we computed a feasible solution by placing middle-points outside of the minimum bounding box of the starting positions, the target positions and the obstacles, and moving each robot from its starting point to its target point through a middle-point. Second, we applied a simple local search approach where we repeatedly delete and insert again a random robot through an optimal path. It improves the quality of the solution, as the robots no longer need to go through the middle-points. Finally, we used simulated annealing to further improve this feasible solution. We used two different types of moves: We either tightened the whole trajectory of a robot, or we stretched it between two points by making the robot move through a third intermediate point generated at random. [ABSTRACT FROM AUTHOR]

We address the problem of designing, implementing, and experimenting with compressed data structures that support rank and select queries over a dictionary of integers. We shine a new light on this classical problem by showing a connection between the input integers and the geometry of a set of points in a Cartesian plane suitably derived from them. We then build upon some results in computational geometry to introduce the first compressed rank/select dictionary based on the idea of "learning" the distribution of such points via proper linear approximations (LA). We therefore call this novel data structure the la_vector. We prove time and space complexities of the la_vector in several scenarios: in the worst case, in the case of input distributions with finite mean and variance, and taking into account the kth order entropy of some of its building blocks. We also discuss improved hybrid data structures, namely, ones that suitably orchestrate known compressed rank/select dictionaries with the la_vector. We corroborate our theoretical results with a large set of experiments over datasets originating from a variety of applications (Web search, DNAsequencing, information retrieval, and natural language processing) and show that our approach provides new interesting space-time tradeoffs with respect to many well-established compressed rank/select dictionary implementations. In particular, we show that our select is the fastest, and our rank is on the space-time Pareto frontier. [ABSTRACT FROM AUTHOR]

We study the problem of engineering space–time efficient data structures that support membership and rank queries on very large static dictionaries of strings. Our solution is based on a very simple approach that decouples string storage and string indexing by means of a block-wise compression of the sorted dictionary strings (to be stored in external memory) and a succinct implementation of a Patricia trie (to be stored in internal memory) built on the first string of each block. On top of this, we design an in-memory cache that, given a sample of the query workload, augments the Patricia trie with additional information to reduce the number of I/Os of future queries. Our experimental evaluation on two new datasets, which are at least one order of magnitude larger than the ones used in the literature, shows that (i) the state-of-the-art compressed string dictionaries, compared to Patricia tries, do not provide significant benefits when used in a large-scale indexing setting, and (ii) our two-level approach enables the indexing and storage of 3.5 billion strings taking 273 GB in just less than 200 MB of internal memory and 83 GB of compressed disk space, while still guaranteeing comparable or faster query performance than those offered by array-based solutions used in modern storage systems, such as RocksDB, thus possibly influencing their future design. [ABSTRACT FROM AUTHOR]

We give an overview of theoretical and practical aspects of finding a simple polygon of minimum (Min-Area) or maximum (Max-Area) possible area for a given set of n points in the plane. Both problems are known to be NP-hard and were the subject of the 2019 Computational Geometry Challenge, which presented the quest of finding good solutions to more than 200 instances, ranging from n = 10 all the way to n = 1, 000, 000. [ABSTRACT FROM AUTHOR]

We describe a practical method to find near-optimal solutions for the area-optimal simple polygonization problem: Given a set of points S in the plane, the objective is to find a simple polygon of minimum or maximum area defined by S. Our approach is based on the celebrated metaheuristic Simulated Annealing. The method consists of a modular pipeline of steps, where each step can be implemented in various ways and with several parameters controlling it. We have implemented several different algorithms and created an application that computes a polygon with minimal (or maximal) area. We experimented with the various algorithmic options and with the controlling parameters of each algorithm to tune up the pipeline. Then, we executed the application on each of the benchmark instances, exploiting a grid of servers, to obtain near optimal results. [ABSTRACT FROM AUTHOR]

We study the problem of computing constrained shortest paths for battery electric vehicles. Because battery capacities are limited, fastest routes are often infeasible. Instead, users are interested in fast routes on which the energy consumption does not exceed the battery capacity. For that, drivers can deliberately reduce speed to save energy. Hence, route planning should provide both path and speed recommendations. To tackle the resulting N P -hard optimization problem, previous work trades correctness or accuracy of the underlying model for practical running times. We present a novel framework to compute optimal constrained shortest paths (without charging stops) for electric vehicles that uses more realistic physical models, while taking speed adaptation into account. Careful algorithm engineering makes the approach practical even on large, realistic road networks: We compute optimal solutions in less than a second for typical battery capacities, matching the performance of previous inexact methods. For even faster query times, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds. [ABSTRACT FROM AUTHOR]

We study the problem of computing paths that minimize energy consumption of a battery electric vehicle. For that, we must cope with specific properties, such as regenerative braking and constraints imposed by the battery capacity. These restrictions can be captured by profiles, which are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for battery electric vehicles. In this work, we prove that profiles have linear complexity. We examine different variants of Dijkstra's algorithm to compute energy-optimal paths or profiles. Further, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. We also discuss a heuristic variant that is easy to implement, and carefully integrate it with the well-known Contraction Hierarchies algorithm and A* search. Finally, we propose a practical approach that enables computation of energy-optimal routes within milliseconds after fast (metric-dependent) preprocessing of the whole network. This enables flexible updates due to, e. g., weather forecasts or refinements of the consumption model. Practicality of our approaches is demonstrated in a comprehensive experimental study on realistic, large-scale road networks. [ABSTRACT FROM AUTHOR]

The selection of input data is a crucial step in virtually every empirical study. Experimental campaigns in algorithm engineering, experimental algorithmics, network analysis, and many other fields often require suited network data. In this context, synthetic graphs play an important role, as data sets of observed networks are typically scarce, biased, not sufficiently understood, and may pose logistic and legal challenges. Just like processing huge graphs becomes challenging in the big data setting, new algorithmic approaches are necessary to generate such massive instances efficiently. Here, we update our previous survey [35] on results for large-scale graph generation obtained within the DFG priority programme SPP 1736 (Algorithms for Big Data); to this end, we broaden the scope and include recently published results. [ABSTRACT FROM AUTHOR]

We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions. [ABSTRACT FROM AUTHOR]

Abstract Background A basic task in bioinformatics is the counting of k-mers in genome sequences. Existing k-mer counting tools are most often optimized for small k < 32 and suffer from excessive memory resource consumption or degrading performance for large k. However, given the technology trend towards long reads of next-generation sequencers, support for large k becomes increasingly important. Results We present the open source k-mer counting software Gerbil that has been designed for the efficient counting of k-mers for k ≥ 32. Our software is the result of an intensive process of algorithm engineering. It implements a two-step approach. In the first step, genome reads are loaded from disk and redistributed to temporary files. In a second step, the k-mers of each temporary file are counted via a hash table approach. In addition to its basic functionality, Gerbil can optionally use GPUs to accelerate the counting step. In a set of experiments with real-world genome data sets, we show that Gerbil is able to efficiently support both small and large k. Conclusions While Gerbil’s performance is comparable to existing state-of-the-art open source k-mer counting tools for small k < 32, it vastly outperforms its competitors for large k, thereby enabling new applications which require large values of k.

We study the problem of minimizing overall trip time for battery electric vehicles in road networks. As battery capacity is limited, stops at charging stations may be inevitable. Careful route planning is crucial because charging stations are scarce and recharging is time-consuming. We extend the constrained shortest-path problem for electric vehicles with realistic models of charging stops, including varying charging power and battery-swapping stations. Although the resulting problem is theoretically hard, we propose a combination of algorithmic techniques to achieve good performance in practice. Extensive experimental evaluation shows that our approach (CHArge) enables computation of optimal solutions on realistic inputs even of continental scale. Finally, we investigate heuristic variants of CHArge that derive high-quality routes in well below a second on sensible instances. [ABSTRACT FROM AUTHOR]

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 s o l 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 (n L + n d 3 ⋅ 6.731 d) time. [ABSTRACT FROM AUTHOR]

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. • Investigation about Pickup and delivery tasks with deadlines in a multi-robot systems. • Task swapping between robots can results in negative effects. • Allocation of tasks and ensuring collision free trajectories is computationally hard. • A novel measure for ordering temporally constrained tasks performs good. • New scoring function for optimization of multiple objectives is effective. • Proving, theoretically and experimentally, the correctness of the new algorithm. • Extensive simulation showing the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

A (convex) polytope P is said to be 2-level if for each hyperplane H that supports a facet of P, the vertices of P can be covered with H and exactly one other translate of H. The study of these polytopes is motivated by questions in combinatorial optimization and communication complexity, among others. In this paper, we present the first algorithm for enumerating all combinatorial types of 2-level polytopes of a given dimension d, and provide complete experimental results for d⩽7. Our approach is inductive: for each fixed (d-1)-dimensional 2-level polytope P0, we enumerate all d-dimensional 2-level polytopes P that have P0 as a facet. This relies on the enumeration of the closed sets of a closure operator over a finite ground set. By varying the prescribed facet P0, we obtain all 2-level polytopes in dimension d. [ABSTRACT FROM AUTHOR]

We study the problem of computing isocontours in static and dynamic road networks, where the objective is to identify the boundary of the region that is reachable from a given source within a certain amount of time (or another limited resource). Although there is a wide range of practical applications for this problem (e.g., urban planning, geomarketing, visualizing the cruising range of a vehicle), there has been little research on fast algorithms for large, realistic inputs, and existing approaches tend to compute more information than necessary. Our contribution is twofold: (1) We propose compact but sufficient definitions of isocontours, based on which (2) we provide several easy-to-parallelize, scalable algorithmic approaches for faster computation. By extensive experimental analysis, we demonstrate that our techniques enable interactive isocontour computation within milliseconds even on continental networks, significantly faster than the state of the art. [ABSTRACT FROM AUTHOR]

Given a graph G, the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of G with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski's famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-Boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance. [ABSTRACT FROM AUTHOR]