DocumentCode
1151394
Title
Deleting vertices to bound path length
Author
Paik, Doowon ; Reddy, Sudhakar ; Sahni, Sartaj
Author_Institution
AT&T Bell Labs., Murray Hill, NJ, USA
Volume
43
Issue
9
fYear
1994
fDate
9/1/1994 12:00:00 AM
Firstpage
1091
Lastpage
1096
Abstract
Examines the vertex deletion problem for weighted directed acyclic graphs (WDAGs). The objective is to delete the fewest number of vertices so that the resulting WDAG has no path of length >δ. Several simplified versions of this problem are shown to be NP-hard. However, the problem is solved in linear time when the WDAG is a rooted tree, and in quadratic time when the WDAG is a series-parallel graph
Keywords
computational complexity; directed graphs; NP-hard problems; linear time; path length bound; quadratic time; rooted tree; series-parallel graph; vertex deletion problem; weighted directed acyclic graphs; Cities and towns; Costs; Delay; Flip-flops; Gold; Integrated circuit interconnections; Signal design; Signal restoration; Tree graphs; Very large scale integration;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.312117
Filename
312117
Link To Document