Publisher DOI: 10.1007/978-3-662-44602-7_7
Title: Treewidth computation and kernelization in the parallel external memory model
Language: English
Authors: Jacob, Riko 
Lieber, Tobias 
Mnich, Matthias  
Issue Date: 2014
Publisher: Springer Nature
Source: IFIP International Conference on Theoretical Computer Science, TCS: 78-89 (2014)
Abstract (english): We present a randomized algorithm which computes, for any fixed k, a tree decomposition of width at most k of any input graph. We analyze it in the parallel external memory (PEM) model that measures efficiency by counting the number of cache misses on a multi-CPU private cache shared memory machine. Our algorithm has sorting complexity, which we prove to be optimal for a large parameter range. We use this algorithm as part of a PEM-efficient kernelization algorithm. Kernelization is a technique for preprocessing instances of size n of NP-hard problems with a structural parameter κ by compressing them efficiently to a kernel, an equivalent instance of size at most g(κ). An optimal solution to the original instance can then be recovered efficiently from an optimal solution to the kernel. Our main results here is an adaption of the linear-time randomized protrusion replacement algorithm by Fomin et al. (FOCS 2012). In particular, we obtain efficient randomized parallel algorithms to compute linear kernels in the PEM model for all separable contraction-bidimensional problems with finite integer index (FII) on apex minor-free graphs, and for all treewidth-bounding graph problems with FII on topological minor-free graphs.
Conference: IFIP International Conference on Theoretical Computer Science (TCS 2014) 
Type: InProceedings (Aufsatz / Paper einer Konferenz etc.)
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Sep 30, 2020

Google ScholarTM


Add Files to Item

Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.