Edge Weight Reduction Problems in Directed Acyclic Graphs

DOI10.1006/jagm.1997.0856zbMath0882.68105OpenAlexW2085961374MaRDI QIDQ4349699

Susanne E. Hambrusch, Hung-Yi Tu

Publication date: 25 August 1997

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

Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2105&context=cstech

zbMATH Keywords

directed acyclic graph

Mathematics Subject Classification ID

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

Related Items (15)

Optimal approaches for upgrading selective obnoxious \(p\)-median location problems on tree networks ⋮ Upgrading the 1-center problem with edge length variables on a tree ⋮ Upgrading min-max spanning tree problem under various cost functions ⋮ Upgrading edges in the graphical TSP ⋮ The \(p\)-median problem with upgrading of transportation costs and minimum travel time allocation ⋮ Upgrading \(p\)-median problem on a path ⋮ Speedup the optimization of maximal closure of a node-weighted directed acyclic graph ⋮ Improving spanning trees by upgrading nodes ⋮ Complexity of reducing the delay between two nodes by node-based and edge-based upgrading strategies ⋮ A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Modifying edges of a network to obtain short subgraphs ⋮ Up- and downgrading the 1-center in a network ⋮ Minimizing broadcast costs under edge reductions in tree networks ⋮ On budget-constrained flow improvement.

This page was built for publication: Edge Weight Reduction Problems in Directed Acyclic Graphs