Displaying similar documents to “Memory paging for connectivity and path problems in graphs.”

The Capacitated Arc Routing Problem. A heuristic algorithm.

Enrique. Benavent, V. Campos, Angel Corberán, Enrique Mota (1990)

Qüestiió

Similarity:

In this paper we consider the Capacitated Arc Routing Problem, in which a fleet of K vehicles, all of them based on a specific vertex (the depot) and with a known capacity Q, must service a subset of the edges of the graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. A heuristic algorithm for this problem is proposed consisting of: the selection of K centers, the construction of K connected graphs with associated loads...

Labeled shortest paths in digraphs with negative and positive edge weights

Phillip G. Bradford, David A. Thomas (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper gives a shortest path algorithm for CFG (context free grammar) labeled and weighted digraphs where edge weights may be positive or negative, but negative-weight cycles are not allowed in the underlying unlabeled graph. These results build directly on an algorithm of Barrett  [ (2000) 809–837]. In addition to many other results, they gave a shortest path algorithm for CFG labeled and weighted digraphs where all edges are nonnegative. Our algorithm is based...

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Markov, Minko, Ionut Andreica, Mugurel, Manev, Krassimir, Tapus, Nicolae (2012)

Serdica Journal of Computing

Similarity:

ACM Computing Classification System (1998): G.2.2. We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer...