On Satisfiability Problems with a Linear Structure

DOI10.4230/LIPIcs.IPEC.2016.14zbMath1398.68235arXiv1602.07876OpenAlexW2963301030MaRDI QIDQ4634397

Serge Gaspers, Sigve Hortemo Sæther, Jan Arne Telle, Christos H. Papadimitriou

Publication date: 10 April 2018

Full work available at URL: https://arxiv.org/abs/1602.07876

zbMATH Keywords

satisfiabilityinterval graphsFPT algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A width parameter useful for chordal and co-comparability graphs ⋮ Lower bounds on the mim-width of some graph classes ⋮ Unnamed Item ⋮ On efficiently solvable cases of quantum \(k\)-SAT

This page was built for publication: On Satisfiability Problems with a Linear Structure