查詢結果分析
來源資料
頁籤選單縮合
題 名 | A Linear Algorithm for the Hamiltonian Problem on Distance-Hereditary Graphs |
---|---|
作 者 | 洪若偉; | 書刊名 | 南開學報 |
卷 期 | 7(上) 民91.06 |
頁 次 | 頁241+243-254 |
分類號 | 440.11 |
關鍵詞 | 圖形演算法; 保距圖; 補圖形; 漢彌爾頓迴路; 路徑覆蓋; Graph algorithms; Distance-hereditary graphs; Cographs; Hamiltonian cycle problem; Path cover; |
語 文 | 英文(English) |
中文摘要 | 一個連結圖G=(V,E)中,假使任兩個頂點在G中的距離與它們在G的任何延生圖中的距離相同,則此圖稱為保距圖。此篇論文提出一個O(︱E︱+︱V︱)時間的線性演算法,來解決保距圖上的漢彌爾頓迴路的問題。 |
英文摘要 | A connected graph G=(V,E) is called distance-hereditary if every two vertices in V have the same distance in every connected inducted induced subgraph of G containing them. This paper presents an O(︱E︱+︱V︱) time algorithm for solving the Hamiltonian cycle problem on distance-hereditary graphs. |
本系統中英文摘要資訊取自各篇刊載內容。