✦ LIBER ✦

Edge Weight Reduction Problems in Directed Acyclic Graphs

✍ Scribed by Susanne E. Hambrusch; Hung-Yi Tu

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 378 KB
Volume: 24
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1997.0856

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a weighted directed acyclic graph in which edge weights are not static quantities, but can be reduced for a certain cost. In this paper we consider the problem of determining which edges to reduce so that the length of the longest paths is minimized and the total cost associated with the reductions does not exceed a given cost. We consider two types of edge reductions, linear reductions and 0r1 reductions, which model different applications. We present efficient algorithms for different classes of graphs, including trees, series᎐parallel graphs, and directed acyclic graphs, and we show other edge reduction problems to be NP-hard.

📜 SIMILAR VOLUMES

Edge-disjoint cycles in regular directed

Edge-disjoint cycles in regular directed graphs

✍ Alon, Noga; McDiarmid, Colin; Molloy, Michael 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB 👁 3 views

We prove that any k-regular directed graph with no parallel edges contains a collection of at least fl(k2) edge-disjoint cycles; we conjecture that in fact any such graph contains a collection of at least ( lCi1 ) disjoint cycles, and note that this holds for k 5 3. o 1996

Efficient edge domination problems in gr

Efficient edge domination problems in graphs

✍ Dana L. Grinstead; Peter J. Slater; Naveed A. Sherwani; Nancy D. Holmes 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 558 KB

Computer generation of characteristic po

Computer generation of characteristic polynomials of edge-weighted graphs, heterographs, and directed graphs

✍ K. Balasubramanian 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 624 KB

The computer code developed previously (K. Balasubramanian, J . Computational Chern., 5,387 (1984)) for the characteristic polynomials of ordinary (nonweighted) graphs is extended in this investigation to edge-weighted graphs, heterographs (vertex-weighted), graphs with loops, directed graphs, and s

Optimal clustering in graphs with weight

Optimal clustering in graphs with weighted edges: A unified approach to the threshold problem

✍ Goetschel, Roy ;Voxman, William 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 691 KB

## Relations on a finite set V are viewed as weighted graphs. Using the language of graph theory two methods of partitioning V are examined. In one method, partitionings of V are obtained by selecting threshold values and applying them to a maximal weighted spanning forest. In another method a para

Vertex-disjoint paths and edge-disjoint

Vertex-disjoint paths and edge-disjoint branchings in directed graphs

✍ R. W. Whitty 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB

A theorem of J. Edmonds states that a directed graph has k edge-disjoint branchings rooted at a vertex r if and only if every vertex has k edge-disjoint paths to r . We conjecture an extension of this theorem to vertex-disjoint paths and give a constructive proof of the conjecture in the case k = 2.

Recent problems and results about kernel

Recent problems and results about kernels in directed graphs

✍ C. Berge; P. Duchet 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 355 KB

In Section 1, we survey the existence theorems for a kernel; in Section 2, we discuss a new conjecture which could constitute a bridge between the kernel problems and the perfect graph conjecture. In fact, we believe that a graph is 'quasi-perfect' if and only if it is perfect. ## Proposition 1.1.