All structured programs have small tree width and good register allocation

DOI10.1006/inco.1997.2697zbMath0924.68023OpenAlexW1989556004MaRDI QIDQ1271620

Mikkel Thorup

Publication date: 10 November 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1997.2697

zbMATH Keywords

register-allocation problem

Mathematics Subject Classification ID

Theory of programming languages (68N15) General topics in the theory of software (68N01)

Related Items (31)

A new approach on locally checkable problems ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ A general framework for path convexities ⋮ Eccentricity queries and beyond using hub labels ⋮ The tree-width of C ⋮ Pushdown reachability with constant treewidth ⋮ On the computational complexity of the bipartizing matching problem ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ Tangle bases: Revisited ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ Efficient interprocedural data-flow analysis using treedepth and treewidth ⋮ Approximation algorithms via contraction decomposition ⋮ Small vertex cover makes Petri net coverability and boundedness easier ⋮ The complexity of register allocation ⋮ Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Register loading via linear programming ⋮ Coloring temporal graphs ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ Graph Operations, Graph Transformations and Monadic Second-Order Logic: ⋮ Recognizing digraphs of Kelly-width 2 ⋮ Tree-decompositions of small pathwidth ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ Complexity of secure sets ⋮ Tree-decompositions of small pathwidth ⋮ Tight bounds for reachability problems on one-counter and pushdown systems ⋮ Unnamed Item ⋮ Faster algorithms for quantitative verification in bounded treewidth graphs ⋮ Synthesizing structured reactive programs via deterministic tree automata ⋮ Listing all potential maximal cliques of a graph

Uses Software

• Modula
• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Region-based memory management
• Monadic second-order evaluations on tree-decomposable graphs
• Graph minors. I. Excluding a forest
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Revised report on the algorithmic language ALGOL 60
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• A still better performance guarantee for approximate graph coloring
• Complexity of path-forming games
• Fugitive-search games on graphs and related parameters
• Generalized dominators for structured programs
• Graph minors. XIII: The disjoint paths problem
• The programming language Pascal
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Easy problems for tree-decomposable graphs
• Complexity of Finding Embeddings in a k-Tree
• The Complexity of Coloring Circular Arcs and Chords
• On the hardness of approximating minimization problems
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: All structured programs have small tree width and good register allocation