Improving a fixed parameter tractability time bound for the shadow problem

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)

zbMATH Keywords

Dynamic programmingFixed parameter tractabilityPure implicational formulaShadow independent setShadow pattern

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

On generalizations of the shadow independent set problem ⋮ Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

Cites Work

• An algorithm for the class of pure implicational formulas
• The complexity of theorem-proving procedures
• The complexity of the falsifiability problem for pure implicational formulas
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improving a fixed parameter tractability time bound for the shadow problem