Improving a fixed parameter tractability time bound for the shadow problem
From MaRDI portal
Publication:1877708
DOI10.1016/S0022-0000(03)00079-5zbMath1092.68048MaRDI QIDQ1877708
Stefan Porschen, Peter Heusch, Ewald Speckenmeyer
Publication date: 19 August 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Dynamic programming; Fixed parameter tractability; Pure implicational formula; Shadow independent set; Shadow pattern
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
On generalizations of the shadow independent set problem, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
Cites Work