EUVIMEDEUVIMED entdecken
Crossref

Constraint Solving via Fractional Edge Covers

Martin Grohe, Dániel Marx

ACM Transactions on Algorithms · 28.10.2014 · 11 (1) · 1-20

DOI: 10.1145/2636918 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 25.08.2014. Verfasst von Martin Grohe und 1 weiteren Autor:innen. Die Arbeit wurde bisher 93-mal zitiert (Crossref) und nennt 44 Literaturangaben. Gefördert von: European Research Council, Országos Tudományos Kutatási Alapprogramok.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence, identifying polynomial-time solvable classes of constraint satisfaction problems has received a lot of attention. In this article, we are interested in structural properties that can make the problem tractable. So far, the largest structural class that is known to be polynomial-time solvable is the class of bounded hypertree width instances introduced by Gottlob et al. [2002]. Here we identify a new class of polynomial-time solvable instances: those having bounded fractional edge cover number. Combining hypertree width and fractional edge cover number, we then introduce the notion of fractional hypertree width. We prove that constraint satisfaction problems with bounded fractional hypertree width can be solved in polynomial time (provided that the tree decomposition is given in the input). Together with a recent approximation algorithm for finding such decompositions [Marx 2010], it follows that bounded fractional hypertree width is now the most generally known structural property that guarantees polynomial-time solvability.

Förderung

  • European Research Council
  • Országos Tudományos Kutatási Alapprogramok

Zitieren

APA

Grohe, M., & Marx, D. (2014). Constraint Solving via Fractional Edge Covers. ACM Transactions on Algorithms, 11(1), 1-20. https://doi.org/10.1145/2636918

Vancouver

Grohe M, Marx D. Constraint Solving via Fractional Edge Covers. ACM Transactions on Algorithms. 2014;11(1):1-20. doi:10.1145/2636918

BibTeX
@article{Grohe2014,
  author = {Grohe, Martin and Marx, Dániel},
  title = {Constraint Solving via Fractional Edge Covers},
  journal = {ACM Transactions on Algorithms},
  year = {2014},
  volume = {11},
  number = {1},
  pages = {1--20},
  doi = {10.1145/2636918}
}
Kostenlos starten →