W rezultacie przez Robertson Seymour wykazuje algorytm do testowania, czy stałej wykres jest minor . Mam dwa i pół pytania na ten temat:
1) Wygląda na to, że od tego czasu wprowadzono ulepszenia tego algorytmu. Jaki jest obecnie najbardziej znany algorytm?
2a) Co ludzie przypuszczają, że są optymalnym związkiem?
Algorytm Mohara do osadzania na stałej powierzchni oraz algorytm Kawarabayashiego do rozpoznawania wykresów -apex decydują o przynależności do wykresów charakterystycznych dla zabronionych nieletnich w czasie liniowym, motywując ostatnie pytanie:
2b) Czy istnieje powód, by podejrzewać, że możemy to zrobić w czasie liniowym?
Oczywiście, jeśli ktoś już wymyślił algorytm czasu liniowego, dwa ostatnie pytania są głupie. :)
Odpowiedzi:
Jest przedruk z Ken-ichi Kawarabayashim, Yusuke Kobayashim i Brucem Reedem, który twierdzi, że algorytm jest kwadratowy: „ Problem z rozłącznymi ścieżkami w czasie kwadratowym ”. Jest on sformatowany jako przesłanie konferencyjne, a nie artykuł w czasopiśmie, więc nie jestem pewien, czy można zweryfikować szczegóły (sam tak naprawdę nie próbowałem).
Niedawna ankieta Kawarabayashi podaje, że jest to najbardziej znany wynik problemu blisko powiązanych ścieżek rozłącznych: Ken-ichi Kawarabayashi (2011), „Problem ścieżek rozłącznych: algorytm i struktura”, WALCOM: Algorytmy i obliczenia, LNCS 6552, pp. 2–7, doi: 10.1007 / 978-3-642-19094-0_2 .
Nie wiem, czy to oznacza, że twierdzenie w komentarzu Kothari jest parą, czy też oznacza, że jest jeszcze na wcześniejszym etapie pisania.O ( n logn )
źródło
Niedawny artykuł Isolde Adler1, Frederic Dorn, Fedora V. Fomin, Ignasi Sau i Dimitriosa M. Thilikosa zatytułowany Szybkie drobne testy na wykresach planarnych pokazuje, że szukając niewielkiego na wierzchołkach h na płaskim wykresie G , można to zrobić w czasie 2 O ( h ) n + O ( n 2 log n ) . Podczas gdy zależność od n nie jest tak dobra jak ta wymieniona w odpowiedzi Davida, zależność od h tej pracy jest znacznie wyższa.H. h sol 2)O ( h )n + O ( n2)logn ) n h
źródło