2022/08/22 by David Eppstein · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Algorithm #Combinatorics #Graph #Mathematics #Computer science
paper · pdf · doi:10.1007/s00453-022-01024-9
openalex publication_date 2022/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Abstract We prove that, for an undirected graph with n vertices and m edges, each labeled with a linear function of a parameter λ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>λ</mml:mi> </mml:math> , the number of different minimum spanning trees obtained as the parameter varies can be Ω (mlog n) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> .