Advanced

Randomized word-parallel algorithms for detection of small induced subgraphs

Larsson, David LU and Tokarchuk, Antonina LU (2015) In LU-CS-EX 2015-23 EDA920 20151
Department 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:
author
Larsson, David LU and Tokarchuk, Antonina LU
supervisor
organization
course
EDA920 20151
year
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},
  keyword      = {induced subgraph detection,word parallelism,randomization,Monte Carlo algorithms,practical approach,benchmarking,master’s thesis},
  language     = {eng},
  note         = {Student Paper},
  series       = {LU-CS-EX 2015-23},
  title        = {Randomized word-parallel algorithms for detection of small induced subgraphs},
  year         = {2015},
}