Name
Abstract | ||
|---|---|---|
This paper is devoted to the fast and exact diameter computation in graphs with n vertices and m edges, if the diameter is a large fraction of n. We give an optimal O(m vertical bar n) time algorithm for diameters above n/2. The problem changes its structure at diameter value n/2, as large cycles may be present. We propose a randomized O(m + n log n) time algorithm for diameters above (1/3 + epsilon)n for constant epsilon > 0. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-44543-4_29 | Combinatorial Algorithms |
Field | DocType | Volume |
Graph,Discrete mathematics,Binary logarithm,Combinatorics,Vertex (geometry),Mathematics,Computation | Conference | 9843 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
10 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Damaschke | 1 | 471 | 56.99 |