TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Linear kernels and linear-time algorithms for finding large cuts
 
Options

Linear kernels and linear-time algorithms for finding large cuts

Citation Link: https://doi.org/10.15480/882.2624
Publikationstyp
Journal Article
Date Issued
2017-10-25
Sprache
English
Author(s)
Etscheid, Michael  
Mnich, Matthias  
TORE-DOI
10.15480/882.2624
TORE-URI
http://hdl.handle.net/11420/4693
Journal
Algorithmica  
Volume
80
Issue
9
Start Page
2574
End Page
2615
Citation
Algorithmica (2018)
Publisher DOI
10.1007/s00453-017-0388-z
Publisher
Springer
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.
Subjects
Max-cut
Kernelization
Linear-time algorithms
DDC Class
004: Informatik
More Funding Information
Supported by ERC Starting Grant 306465 (BeyondWorstCase).
Lizenz
https://creativecommons.org/licenses/by/4.0/
Loading...
Thumbnail Image
Name

Etscheid-Mnich2018_Article_LinearKernelsAndLinear-TimeAlg-1.pdf

Size

689.52 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback