DAG reversal is NP-complete

DOI10.1016/j.jda.2008.09.008zbMath1192.68490OpenAlexW2032126554MaRDI QIDQ1044024

Uwe Naumann

Publication date: 10 December 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.09.008

zbMATH Keywords

NP-completenessadjoint codedata-flow reversalnumerical computer programs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (4)

Subdomain separability in global optimization ⋮ Adjoint Code Design Patterns ⋮ Minimizing the Number of Bootstrappings in Fully Homomorphic Encryption ⋮ Algorithmic Differentiation of Numerical Methods

Uses Software

• TAPENADE
• CompAD
• NAGWare
• TAF
• MITgcm

Cites Work

• Optimality-preserving elimination of linearities in Jacobian accumulation
• Automatic differentiation: Applications, theory, and implementations. Selected papers based on the presentation at the 4th international conference on automatic differentiation (AD), Chicago, IL, USA, July 20--23, 2004
• Recipes for adjoint code construction
• The Pebbling Problem is Complete in Polynomial Space
• Computational differentiation: techniques, applications, and tools
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: DAG reversal is NP-complete