Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.2624
Publisher DOI: 10.1007/s00453-017-0388-z
Title: Linear kernels and linear-time algorithms for finding large cuts
Language: English
Authors: Etscheid, Michael 
Mnich, Matthias  
Keywords: Max-cut;Kernelization;Linear-time algorithms
Issue Date: 25-Oct-2017
Publisher: Springer
Source: Algorithmica 9 (80): 2574-2615 (2018)
Journal or Series Name: Algorithmica 
Abstract (english): The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: – We show that an algorithm by Crowston et al. (Algorithmica 72(3):734–757, 2015) for (Signed) Max- Cut Above Edwards−ErdÖs Bound can be implemented so as to run in linear time 8k ·O(m); this significantly improves the previous analysis with run time 8k · O(n4). – We give an asymptotically optimal kernel for (Signed) Max- Cut Above Edwards−ErdÖs Bound with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. (Theor Comput Sci 513:53–64, 2013). – We improve all known kernels for parameterizations above strongly λ-extendible properties (a generalization of the Max- Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics,Guwahati, 2013) from O(k3) vertices to O(k) vertices.
URI: http://hdl.handle.net/11420/4693
DOI: 10.15480/882.2624
ISSN: 1432-0541
Type: (wissenschaftlicher) Artikel
Funded by: Supported by ERC Starting Grant 306465 (BeyondWorstCase).
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
Etscheid-Mnich2018_Article_LinearKernelsAndLinear-TimeAlg-1.pdfVerlags-PDF689,52 kBAdobe PDFThumbnail
View/Open
Show full item record

Page view(s)

66
Last Week
7
Last month
checked on Feb 25, 2020

Download(s)

11
checked on Feb 25, 2020

Google ScholarTM

Check

Export

This item is licensed under a Creative Commons License Creative Commons