Complete Register Allocation Problems

DOI10.1137/0204020MaRDI QIDQ4092979zbMATH OpenOpenAlexFDO

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
• Min Cut is NP-complete for edge weighted trees
• Proof of space from stacked expanders
• On the cost of recomputing: tight bounds on pebbling with faults
• More general parallel tree contraction: Register allocation and broadcasting in a tree
• Bounded MSC communication
• A higher-order strategy for eliminating common subexpressions
• Optimal contiguous expression DAG evaluations
• 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
• Time-space trade-offs in a pebble game
• Nullstellensatz size-degree trade-offs from reversible pebbling
• On the target pebbling conjecture
• Reversible pebble game on trees
• Nullstellensatz size-degree trade-offs from reversible pebbling
• 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
• Pebble games for studying storage sharing
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Ant colony algorithm for single processor scheduling with minimization of peak resource usage
• 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)