Bandwidth constraints on problems complete for polynomial time
From MaRDI portal
Publication:791316
DOI10.1016/0304-3975(83)90078-6zbMath0535.68021OpenAlexW2053805167WikidataQ127662435 ScholiaQ127662435MaRDI QIDQ791316
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
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Alternating on-line Turing machines with only universal states and small space bounds ⋮ Bandwidth Minimization: An approximation algorithm for caterpillars ⋮ Bandwidth contrained NP-complete problems ⋮ Complete problems for space bounded subclasses of NP ⋮ Topological Bandwidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree-size bounded alternation
- An extension of Savitch's theorem to small space bounds
- On uniform circuit complexity
- On tape-bounded complexity classes and multihead finite automata
- An observation on time-storage trade off
- Space bounds for processing contentless inputs
- Space-bounded reducibility among combinatorial problems
- The NP-completeness of the bandwidth minimization problem
- Lower bounds on space complexity for contextfree recognition
- Relationships between nondeterministic and deterministic tape complexities
- Minimizing the bandwidth of sparse symmetric matrices
- Alternation
- The bandwidth problem for graphs and matrices—a survey
- On Relating Time and Space to Size and Depth
- On the Tape Complexity of Deterministic Context-Free Languages
- Complexity Results for Bandwidth Minimization
- Relations Among Complexity Measures
- An algorithm for reducing the bandwidth of a matrix of symmetrical configuration
- Some Results on Tape-Bounded Turing Machines
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
