We revisit the exact algorithm to compute the treewidth of a graph of Tamaki and present it in a way that facilitates improvements. The so-called I-blocks and O-blocks enumerated by the algorithm are interpreted as su...
详细信息
The vertex connectivity of a graph is the size of the minimum set of vertices that, when removed, disconnects the graph. A 2020 paper by Forster, Nanongkai, Saranurak, Yang and Yingchareonthawornchai presents a new al...
详细信息
The vertex connectivity of a graph is the size of the minimum set of vertices that, when removed, disconnects the graph. A 2020 paper by Forster, Nanongkai, Saranurak, Yang and Yingchareonthawornchai presents a new algorithm to compute vertex connectivity in near-linear time when vertex connectivity is low. The algorithm uses a sublinear time subroutine to try to find a separator ``near’’ a given vertex. The previous state of the art is a algorithm by Henzinger, Rao and Gabow (2000) that runs in O(nm) time. Other algorithms with quadratic running time when m = O(n) have been known since the 1960s.
This thesis explores the practical performance of the near-linear time algorithm for undirected graphs by comparing it to an implementation of the algorithm by Henzinger et al. New heuristics are also explored for the algorithm to further improve its performance. An efficient implementation of the algorithm by Forster et al. performs well on graphs with low vertex connectivity compared to the algorithm by Henzinger et al. A variant using a new ``degree counting’’ heuristic performs better, especially on graphs with slightly larger vertex connectivity.
According to experiments on random graphs with planted unbalanced vertex cuts, random hyperbolic graphs and real world graphs with vertex connectivity between 4 and 15, the degree counting version offers a factor 1.5-3.5 speedup over the original near-linear time algorithm. It outperforms the quadratic time algorithm even on relatively small graphs (200-8192 vertices depending on the graph family and vertex connectivity).
This paper studies the journey planning problem in the context of transit networks. Given the timetable of a schedule-based transportation system (consisting, e.g., of trains, buses, etc.), the problem seeks journeys ...
详细信息
This paper studies the journey planning problem in the context of transit networks. Given the timetable of a schedule-based transportation system (consisting, e.g., of trains, buses, etc.), the problem seeks journeys optimizing some criteria. Specifically, it seeks to answer natural queries such as, for example, "find a journey starting from a source stop and arriving at a target stop as early as possible". The fastest approach for answering to these queries, yielding the smallest average query time even on very large networks, is the Public Transit Labeling framework, proposed for the first time in Delling et al., SEA 2015. This method combines three main ingredients: (i) a graph-based representation of the schedule of the transit network;(ii) a labeling of such graph encoding its transitive closure (computed via a time-consuming pre-processing);(iii) an efficient query algorithm exploiting both (i) and (ii) to answer quickly to queries of interest at runtime. Unfortunately, while transit networks' timetables are inherently dynamic (they are often subject to delays or disruptions), ptl is not natively designed to handle updates in the schedule-even after a single change, precomputed data may become outdated and queries can return incorrect results. This is a major limitation, especially when dealing with massively sized inputs (e.g., metropolitan or continental sized networks), as recomputing the labeling from scratch, after each change, yields unsustainable time overheads that are not compatible with interactive applications. In this work, we introduce a new framework that extends ptl to function in delay-prone transit networks. In particular, we provide a new set of algorithms able to update both the graph and the precomputed labeling whenever a delay affects the network, without performing any recomputation from scratch. We demonstrate the effectiveness of our solution through an extensive experimental evaluation conducted on real-world networks. Our experiments
The k-path problem is to find a simple path of length k. Thisproblem is NP-complete and has applications in bioinformatics fordetecting signaling pathways in protein interaction networks and for biological subnetwork ...
详细信息
The k-path problem is to find a simple path of length k. This
problem is NP-complete and has applications in bioinformatics for
detecting signaling pathways in protein interaction networks and for biological subnetwork matching. There are algorithms implemented to
solve the problem for k up to 13. The fastest implementation has
running time O^*(4.32^k), which is slower than the best known algorithm of running time O^*(4^k). To implement the best known algorithm for the k-path problem, we need to construct (n,k)-universal set.
In this thesis, we study the practical algorithms for constructing the (n,k)-universal set problem. We propose six algorithm variants to
handle the increasing computational time and memory space needed for
k=3, 4, ..., 8. We propose two major empirical techniques that cut
the time and space tremendously, yet generate good results. For the case k=7, the size of the universal set found by our algorithm is 1576, and is 4611 for the case k=8.
We implement the proposed algorithms with the OpenMP parallel interface and construct universal sets for k=3, 4, ..., 8. Our experiments show that our algorithms for the (n,k)-universal set problem exhibit very good parallelism and hence shed light on its MPI implementation.
Ours is the first implementation effort for the (n,k)-universal set
problem. We share the effort by proposing an extensible universal set construction and retrieval system. This system integrates universal set construction algorithms and the universal sets constructed. The sets are
stored in a centralized database and an interface is provided to access the database easily.
The (n,k)-universal set have been applied to many other NP-complete
problems such as the set splitting problems and the matching
and packing problems. The small (n,k)-universal set constructed
by us will reduce significantly the time to solve those problems.
We present a package for algorithms on planar networks. This package comes with a graphical user interface, which may be used for demonstrating and animating algorithms. Our focus so far has been on disjoint path prob...
详细信息
We present a package for algorithms on planar networks. This package comes with a graphical user interface, which may be used for demonstrating and animating algorithms. Our focus so far has been on disjoint path problems. However, the package is intended to serve as a general framework, wherein algorithms for various problems on planar networks may be integrated and visualized. For this aim, the structure of the package is designed so that integration of new algorithms and even new algorithmic problems amounts to applying a short "recipe." The package has been used to develop new variations of well-known disjoint path algorithms, which heuristically optimize additional N P-hard objectives such as the total length of all paths. We will prove that the problem of finding edge-disjoint paths of minimum total length in a planar graph is N P-hard, even if all terminals lie on the outer face, the Eulerian condition is fulfilled, and the maximum degree is four. Finally, as a demonstration how PlaNet can be used as a tool for developing new heuristics for N P-hard problems, we will report on results of experimental studies on efficient heuristics for this problem. (C) 1999 Elsevier Science B.V. All rights reserved.
暂无评论