Kelas grafik yang diameternya dapat dihitung dalam waktu linier

Ingat diameter dari grafik adalah panjang jalur terpanjang terpendek di G . Diberikan grafik, algoritma yang jelas untuk komputasi diam ( G ) memecahkan semua masalah jalur terpendek (APSP) semua-pasangan dan mengembalikan panjang jalur terpanjang yang ditemukan.$G$$G$$\text{diam}(G)$

Diketahui bahwa masalah APSP dapat diselesaikan dalam waktu optimal untuk beberapa kelas grafik. Untuk grafik umum, ada pendekatan teori graf aljabar yang berjalan dalam waktu O ( M ( n ) log n ) , di mana M ( n ) adalah terikat untuk perkalian matriks. Namun, menghitung diameter tampaknya tidak terkait dengan APSP, seperti yang ditunjukkan oleh Yuster .$O(n^2)$$O(M(n) \log n)$$M(n)$

Apakah beberapa kelas grafik non-sepele diketahui yang diameternya dapat dihitung lebih cepat, katakanlah dalam waktu linier?

Saya terutama tertarik pada grafik chordal, dan setiap subclass dari grafik chordal seperti grafik blok. Sebagai contoh, saya pikir diameter grafik chordal dapat dihitung dalam waktu O ( n + m ) , jika G secara unik digambarkan sebagai pohon klik. Grafik seperti itu juga dikenal sebagai ur-chordal .$G$$O(n+m)$$G$

$v$$v$

$\{\text{AT},\text{claw}\}$

$m = \Omega(n^2)$$K_n$$o(n^2)$$O(m+n)$$o(n^2)$

$(\text{rising sun}- K_2)$

_{(sumber: graphclasses.org )}

• Feodor F. Dragan, Falk Nicolai dan Andreas Brandstädt, pemesanan LexBFS dan kekuatan grafik , WG 1996, LNCS 1197, 166–180. doi: 10.1007 / 3-540-62559-3_15

$\log n$

• Derek G. Corneil, Lexicographic Breadth First Search - A Survey , WG 2004, LNCS 3353, 1–19. doi: 10.1007 / 978-3-540-30559-0_1

Grafik blok yang disebutkan dalam pertanyaan adalah herediter jarak. Algoritma waktu linear untuk menghitung diameter untuk grafik herediter jarak diberikan dalam [1] (lihat Teorema 5).

[1] Dragan, Feodor F. Kelompok dominan dalam grafik herediter jarak. Springer Berlin Heidelberg, 1994.