Typowa twardość rozkładu drzew?

Rozkład drzew jest trudny w najgorszym przypadku, ale chciwa metoda wydaje się być prawie optymalna w małych rzeczywistych sieciach.

1. Czy coś wiadomo o twardości rozkładu drzewa „typowego” wystąpienia jakiejś klasy grafów?
2. Czy istnieje przykład rodziny grafów, w której chciwe metody rozkładu drzew źle się sprawdzają?

Właśnie natrafiłem na odpowiedni artykuł - Kloks / Boedlander „Tylko nieliczne wykresy ograniczyły szerokość drzewa”. Pokazują, że prawie wszystkie wykresy z wierzchołkami i krawędziami mają szerokość równą , . Na przykład oznacza, że ​​typowa szerokość drzewa rośnie wraz z$n$$\delta n$$n^\epsilon$$\epsilon=\frac{\delta-1}{\delta+1}$$\delta=3$$\sqrt{n}$

Więc nawet jeśli chciwa metoda znalazłaby najlepszy rozkład dla wszystkich wykresów, wynikowy algorytm byłby wciąż trudny do zwolnienia dla typowych wykresów