Improving a fixed parameter tractability time bound for the shadow problem

DOI10.1016/S0022-0000(03)00079-5MaRDI QIDQ1877708zbMATH OpenFDO

Authors Peter Heusch, Stefan Porschen, Ewald Speckenmeyer

Publication date 19 August 2004

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-0000(03)00079-5

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)

Recommendations

• On generalizations of the shadow independent set problem
• An algorithm for the class of pure implicational formulas
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• A general method to speed up fixed-parameter-tractable algorithms
• scientific article; zbMATH DE number 125608

Cites work

• An algorithm for the class of pure implicational formulas
• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 702472 (Why is no real title available?)
• scientific article; zbMATH DE number 1113992 (Why is no real title available?)
• scientific article; zbMATH DE number 833906 (Why is no real title available?)
• scientific article; zbMATH DE number 3045411 (Why is no real title available?)
• The complexity of the falsifiability problem for pure implicational formulas
• The complexity of theorem-proving procedures

Cited in

(3)

• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• Shadowing and the viability kernel algorithm
• On generalizations of the shadow independent set problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1877708)