Bandwidth constraints on problems complete for polynomial time

DOI10.1016/0304-3975(83)90078-6MaRDI QIDQ791316zbMATH OpenOpenAlexWikidataFDO

Authors I. H. Sudborough

Publication date 1983

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(83)90078-6

zbMATH Keywords

bandwidth constraintspath system problemtime-space alternating classes

Mathematics Subject Classification ID

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

Recommendations

• Complete problems for space bounded subclasses of NP
• Bandwidth contrained NP-complete problems
• On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas
• A positive relativization of polynomial time versus polylog space
• Decreasing the bandwidth of a transition matrix

Cites work

• scientific article; zbMATH DE number 3761405 (Why is no real title available?)
• scientific article; zbMATH DE number 3571498 (Why is no real title available?)
• scientific article; zbMATH DE number 3630813 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3410504 (Why is no real title available?)
• Alternation
• An algorithm for reducing the bandwidth of a matrix of symmetrical configuration
• An extension of Savitch's theorem to small space bounds
• An observation on time-storage trade off
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Complexity Results for Bandwidth Minimization
• Lower bounds on space complexity for contextfree recognition
• Minimizing the bandwidth of sparse symmetric matrices
• On Relating Time and Space to Size and Depth
• On tape-bounded complexity classes and multihead finite automata
• On the Tape Complexity of Deterministic Context-Free Languages
• On uniform circuit complexity
• Relations Among Complexity Measures
• Relationships between nondeterministic and deterministic tape complexities
• Some Results on Tape-Bounded Turing Machines
• Space bounds for processing contentless inputs
• Space-bounded reducibility among combinatorial problems
• The NP-completeness of the bandwidth minimization problem
• The bandwidth problem for graphs and matrices—a survey
• Tree-size bounded alternation

Cited in

(5)

• Bandwidth contrained NP-complete problems
• Complete problems for space bounded subclasses of NP
• Topological Bandwidth
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Alternating on-line Turing machines with only universal states and small space bounds

This page was built for publication: Bandwidth constraints on problems complete for polynomial time

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