Graph Algorithms

By Jan van Leeuwen. 1991

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Digraphs - theory, algorithms and applications (2002, background): “Thus the overall complexity of finding λ(D) is O(knm) (see also the book by Even [229]).”
The Algorithm Design Manual (2020, background): “Expositions on the proof that the Steiner tree problem for graphs is hard [Kar72] include [Eve79a].”
CLICK: a clustering algorithm with applications to gene expression analysis. (2000, methodology): “The complexity of this computation using Dinic's algorithm (cf. (Even 1979)) is only O(nm 2/a) time.”
Routing, flow, and capacity design in communication and computer networks (2004, background): “([EIS76], and [Eve79]) where it is shown that, even with D = 2 and even with all edge capacities equal to either 0 or 1, this simple two-commodity integer flow problem is inNPC.”
A Unified Framework for Max-Min and Min-Max Fairness With Applications (2007, background): “As shown in [24], this is a problem of a polynomial complexity.”
The cohesiveness of blocks in social networks: Node connectivity and conditional density (2001, background): “A block of G is a maximal connected subgraph with no cutnodes (Harary 1969; Even 1979; Gibbons 1985).16 The blocks of a graph give a partition of its edges.”
Dependent rounding and its applications to approximation algorithms (2006, unknown): “We (cid:12)rst decompose the graph into its biconnected components [17].”
Distribution System Restoration With Microgrids Using Spanning Tree Search (2014, background): “The fundamental cutset can be found by a depth-ﬁ rst-search [16] on .”
Center CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis (2000, unknown): “(Even 1979)) is only O(nm2/a) time.”