Shortest shortest path trees of a network (Q1917275): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Q5549614 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on two problems in connexion with graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3755206 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3140426 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Theorem on Boolean Matrices / rank
 
Normal rank

Latest revision as of 12:08, 24 May 2024

scientific article
Language Label Description Also known as
English
Shortest shortest path trees of a network
scientific article

    Statements

    Shortest shortest path trees of a network (English)
    0 references
    0 references
    0 references
    21 November 1996
    0 references
    If \(N\) is an undirected network where each edge has positive length, we may consider the distances of vertices from a specified internal point of an edge. A shortest path tree (SPT) rooted at \(s\) (possibly an internal point of an edge) is a spanning tree \(T\) of the network \(N[s]\) (i.e., \(N\) with \(s\) as possibly a new vertex) where for each vertex \(v\) the length of the \(s\)-\(v\) path in \(T\) is equal to the \(s\)-\(v\) distance in \(N[s]\). We define \(d(x)\) to be the sum of the distances of \(x\) to all other vertices of \(N\); \(r(x)\) to be the number of edges of a shortest SPT (i.e., one with fewest edges) of \(N\) rooted at \(x\). Two algorithms are given: one to find a shortest SPT and another to find a maximum set of points \(x\) which are best relative to the sizes of \(d(x)\) and \(r(x)\). Both have complexity \(O(mn\log n)\).
    0 references
    network
    0 references
    shortest path tree
    0 references
    spanning tree
    0 references
    algorithms
    0 references
    complexity
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references