Complete Register Allocation Problems

DOI10.1137/0204020zbMATH Open0327.68042OpenAlexW2056304107MaRDI QIDQ4092979FDOQ4092979

Authors: Ravi Sethi 

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0204020

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited In (34)

• The project scheduling problem with production and consumption of resources: a list-scheduling based algorithm
• On tradeoffs between width- and fill-like graph parameters
• On the cost of recomputing: tight bounds on pebbling with faults
• Proof of space from stacked expanders
• Min Cut is NP-complete for edge weighted trees
• More general parallel tree contraction: Register allocation and broadcasting in a tree
• Optimal contiguous expression DAG evaluations
• Bounded MSC communication
• A higher-order strategy for eliminating common subexpressions
• Optimal memory-aware backpropagation of deep join networks
• Cumulative space in black-white pebbling and resolution
• Balloon hashing: a memory-hard function providing provable protection against sequential attacks
• Searching and pebbling
• Bandwidth and pebbling
• Nullstellensatz size-degree trade-offs from reversible pebbling
• On the target pebbling conjecture
• Time-space trade-offs in a pebble game
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Reversible pebble game on trees
• Global storage cells for attributes in an attribute grammar
• Pebbling meets coloring: reversible pebble game on trees
• A polynomial algorithm for minDSC on a subclass of series Parallel graphs
• Ant colony algorithm for single processor scheduling with minimization of peak resource usage
• Pebble games for studying storage sharing
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• The complexity of minimum-length path decompositions
• Memory management optimization problems for integrated circuit simulators
• Typical sequences revisited -- computing width parameters of graphs
• Memory-optimal evaluation of expression trees involving large objects
• On the cost of recomputing: Tight bounds on pebbling with faults
• Storage requirements for deterministic polynomial time recognizable languages
• Scanning phylogenetic networks is NP-hard
• More general parallel tree contraction: register allocation and broadcasting in a tree
• Static-memory-hard functions, and modeling the cost of space vs. time

This page was built for publication: Complete Register Allocation Problems

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