Fibonacci heaps and their uses in improved network optimization algorithms

Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. ACM.

Type

Journal article

Intellectual base

Primary research

Year

1987

DOI

10.1145/28869.28874

DOI registrant

Association for Computing Machinery

Link

https://doi.org/10.1145/28869.28874

Cited by

1 citation across 1 artifact.

Each citation links to the sentence it supports in the citing article.

Domain-specific

• Heap
  • A Fibonacci heap supports decrease-key in amortised O(1) and yields the textbook O(E + V log V) bound for Dijkstra on dense graphs

    This sourceFibonacci heaps with amortised O(1) decrease-key and the resulting O(m + n log n) bound for single-source shortest paths.

    SupportedVerified against the source

    Read by an automated reader; not a human review. How support was checked

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 1 citation: 1 supported. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:ddef6facbc2a · see in the full table