An Experimental Study of a Near-Linear Time Algorithm for Small Vertex Connectivity
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2021-01-25
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
40+2
Series
Abstract
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).Nodsammanhängighet för en graf är den minsta möjliga storleken för en mängd noder som grafen inte är sammanhängande utan. En artikel från 2020 av Forster, Nanongkai, Saranurak, Yang och Yingchareonthawornchai presenterar en ny algoritm för att beräkna nodsammanhängigheten för grafer med låg nodsammanhängighet i nästan linjär tid. Algoritmen använder en sublinjär subrutin för att försöka hitta en separator ``nära'' en given nod. Före detta var den bästa kända algoritmen en algoritm av Henzinger, Rao och Gabow (2000) med kvadratisk tidskomplexitet. Denna avhandling utforskar den nya algoritmens praktiska prestanda på oriktade grafer genom att jämföra den med en implementation av algoritmen av Henzinger et al. Avhandlingen utforskar även nya heuristiker för att förbättra den nya algoritmen. En effektiv implementation av algoritmen av Forster et al. presterar väl på grafer med låg nodsammanhängighet jämfört med algoritmen av Henzinger et al. En variant som använder en ny ``gradräknande'' heuristik presterar bättre, särskilt på grafer med lite högre nodsammanhängighet. Baserat på experiment på slumpgrafer med planterade obalanserade nodsnitt, slumpmässiga hyperboliska grafer och grafer från verkligheten med nodsammanhängighet mellan 4 och 15 är den gradräknande versionen 1.5-3.5 gånger snabbare än den ursprungliga algoritmen. Den presterar bättre än algoritmen med kvadratisk tid även på relativt små grafer (200-8192 noder beroende på graffamilj och nodsammanhängighet).Description
Supervisor
Chalermsook, ParinyaThesis advisor
Yingchareonthawornchai, SorrachaiKeywords
algorithms engineering, graph algorithms, vertex connectivity, sublinear time