Deleting vertices to bound path length

Doowon Paik; Sudhakar Reddy; Sartaj Sahni

doi:10.1109/12.312117

Back

Journal article

Peer reviewed

Deleting vertices to bound path length

Doowon Paik, Sudhakar Reddy and Sartaj Sahni

IEEE transactions on computers, Vol.43(9), pp.1091-1096

09/1994

DOI: 10.1109/12.312117

View Online

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 >/spl delta/. 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.< >

Cities and towns

Costs

Delay

Flip-flops

Gold

Integrated circuit interconnections

Signal design

Signal restoration

Tree graphs

Very large scale integration

Details

Title: Subtitle: Deleting vertices to bound path length
Creators: Doowon Paik - Bell
Sudhakar Reddy - University of Iowa
Sartaj Sahni - University of Florida
Resource Type: Journal article
Publication Details: IEEE transactions on computers, Vol.43(9), pp.1091-1096
DOI: 10.1109/12.312117
ISSN: 0018-9340
eISSN: 1557-9956
Publisher: IEEE
Language: English
Date published: 09/1994
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984197264602771

Metrics

19 Record Views

14 Times Cited - Web of Science