Loading...
Please wait, while we are loading the content...
Similar Documents
DOI: 10.1007/s00453-002-0964-7 Budget Management with Applications
| Content Provider | CiteSeerX |
|---|---|
| Author | Sarrafzadeh, Majid Bozorgzadeh, Elaheh Srivastava, Ankur Chen, Chunhong |
| Abstract | Abstract. Given a directed acyclic graph with timing constraints, the budget management problem is to assign to each vertex an incremental delay such that the sum of these delays is maximized without violating given constraints. We propose the notion of slack sensitivity and budget gradient to demonstrate the characteristics of budget management. We develop a polynomial-time algorithm for the budget management problem, based on the maximum independent set of an established transitive graph. We show the comparison of our approach with the well-known zero-slack algorithm, and extend it to general weighted graphs. Applications to a class of problems in VLSI CAD are also discussed. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Slack Sensitivity Transitive Graph Polynomial-time Algorithm Vlsi Cad Budget Management Maximum Independent Set Incremental Delay Directed Acyclic Graph Well-known Zero-slack Algorithm Budget Gradient Budget Management Problem S00453-002-0964-7 Budget Management General Weighted Graph Timing Constraint |
| Content Type | Text |
| Resource Type | Article |
