Solving order constraints in logarithmic space

DOI10.1007/3-540-36494-3_34MaRDI QIDQ4418666zbMATH OpenFDO

Authors Andrei Krokhin, Benoît Larose

Publication date 11 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070379.htm

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A complexity dichotomy for poset constraint satisfaction
• A complexity dichotomy for poset constraint satisfaction
• Constraint satisfaction problems in non-deterministic logarithmic space
• Constraint satisfaction problems and finite algebras
• Classifying the Complexity of Constraints Using Finite Algebras

Cited in

(5)

• Majority constraints have bounded pathwidth duality
• A complexity dichotomy for poset constraint satisfaction
• Solved forms for path ordering constraints
• Solving simplification ordering constraints
• A complexity dichotomy for poset constraint satisfaction

This page was built for publication: Solving order constraints in logarithmic space

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