Witam.
Mam problem ze zrozumieniem, jakim sposobem algorytm kolorowania grafu Largest-First ( http://pl.wikipedia.org/wiki/Kolorowanie_grafu#Algorytm_LF_.28largest_first.29 ) może mieć złożoność O(n+m) 1 (m - liczba krawędzi, n - liczba wierzchołków).
Już samo sortowanie nierosnąco ma złożoność od O(n*logn) do O(n2) (w zależności od algorytmu). Na myśl przychodzi mi jeszcze sposób bez sortowania: znaleźć stopnie wierzchołków i n razy wybrać wierzchołek o maksymalnym stopniu (O(n)) oznaczając stopień wybranego wierzchołka jako -1. Niestety to również daje O(n2), nie mówiąc nawet o kolorowaniu zachłannym.
Byłbym wdzięczny za wytłumaczenie skąd taka złożoność.
1 źródło: "Optymalizacja dyskretna: modele i metody kolorowania grafów", pod red. M. Kubale