Randomized word-parallel algorithms for detection of small induced subgraphs
(2015) In LU-CS-EX 2015-23 EDA920 20151Department of Computer Science
- Abstract
- Induced subgraph detection is a widely studied set of problems in theoretical
computer science, with applications in e.g. social networks, molecular
biology and other domains that use graph representations. Our focus lies
on practical comparison of some well-known deterministic algorithms to
recent Monte Carlo algorithms for detecting subgraphs on three and four
vertices. For algorithms that involve operations with adjacency matrices,
we study the gain of applying word parallelism, i.e. exploiting the parallel
nature of common processor operations such as bitwise conjunction and
disjunction. We present results of empirical running times for our implementations
of the algorithms. Our results reveal insights as to when the
Monte... (More) - Induced subgraph detection is a widely studied set of problems in theoretical
computer science, with applications in e.g. social networks, molecular
biology and other domains that use graph representations. Our focus lies
on practical comparison of some well-known deterministic algorithms to
recent Monte Carlo algorithms for detecting subgraphs on three and four
vertices. For algorithms that involve operations with adjacency matrices,
we study the gain of applying word parallelism, i.e. exploiting the parallel
nature of common processor operations such as bitwise conjunction and
disjunction. We present results of empirical running times for our implementations
of the algorithms. Our results reveal insights as to when the
Monte Carlo algorithms trump their deterministic counterparts and also
include statistically significant improvements of several algorithms when
applying word parallelism. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/7442642
- author
- Larsson, David LU and Tokarchuk, Antonina LU
- supervisor
- organization
- course
- EDA920 20151
- year
- 2015
- type
- H3 - Professional qualifications (4 Years - )
- subject
- keywords
- induced subgraph detection, word parallelism, randomization, Monte Carlo algorithms, practical approach, benchmarking, master’s thesis
- publication/series
- LU-CS-EX 2015-23
- report number
- LU-CS-EX 2015-23
- ISSN
- 1650-2884
- language
- English
- id
- 7442642
- date added to LUP
- 2015-06-24 08:03:29
- date last changed
- 2015-06-24 08:03:29
@misc{7442642, abstract = {{Induced subgraph detection is a widely studied set of problems in theoretical computer science, with applications in e.g. social networks, molecular biology and other domains that use graph representations. Our focus lies on practical comparison of some well-known deterministic algorithms to recent Monte Carlo algorithms for detecting subgraphs on three and four vertices. For algorithms that involve operations with adjacency matrices, we study the gain of applying word parallelism, i.e. exploiting the parallel nature of common processor operations such as bitwise conjunction and disjunction. We present results of empirical running times for our implementations of the algorithms. Our results reveal insights as to when the Monte Carlo algorithms trump their deterministic counterparts and also include statistically significant improvements of several algorithms when applying word parallelism.}}, author = {{Larsson, David and Tokarchuk, Antonina}}, issn = {{1650-2884}}, language = {{eng}}, note = {{Student Paper}}, series = {{LU-CS-EX 2015-23}}, title = {{Randomized word-parallel algorithms for detection of small induced subgraphs}}, year = {{2015}}, }