On the Complexity of Some Ordering Problems

DOI10.1007/978-3-662-44465-8_11MaRDI QIDQ2922601zbMATH OpenOpenAlexFDO

Authors Beate Bollig

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44465-8_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the Complexity of Ordered Colorings
• The recursive structure of some ordering problems
• scientific article; zbMATH DE number 2099510
• On the sequential ordering problems
• scientific article; zbMATH DE number 1538846
• On the Greedy Solution of Ordering Problems
• On algorithms to find \(p\)-ordering
• scientific article; zbMATH DE number 512933

Cited in

(13)

• Boolean polynomials, BDDs and CRHS equations -- connecting the dots with CryptaPath
• On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
• The query complexity of order-finding
• scientific article; zbMATH DE number 1303559 (Why is no real title available?)
• The order of Appel's algorithm
• Cyclic ordering is NP-complete
• Improving the variable ordering of OBDDs is NP-complete
• The fold complementarity problem and the order complementarity problem
• On the OBDD representation of some graph classes
• scientific article; zbMATH DE number 5761834 (Why is no real title available?)
• On the minimization of (complete) ordered binary decision diagrams
• The referenced vertex ordering problem: theory, applications, and solution methods
• The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication: On the Complexity of Some Ordering Problems

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