Narrow sieves for parameterized paths and packings

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Abstract

We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works; for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2(d-1)n/2. Our techniques generalize an algebraic approach studied in various recent works.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • IT University of Copenhagen
  • Aalto University
  • University of Helsinki
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Sidor (från-till)119-139
TidskriftJournal of Computer and System Sciences
Volym87
Tidigt onlinedatum2017 mar 18
StatusPublished - 2017 aug
PublikationskategoriForskning
Peer review utfördJa

Related projects

Visa alla (1)