WikiEdge:ArXiv-2409.01889v1/terms
跳至導覽
跳至搜尋
- 弱化層次平面圖（Weakly Leveled Planar Graph）：在這種圖中，每個頂點表示為沿水平線（稱為層級）的點，每條邊要麼是水平線段，要麼是嚴格單調的曲線。
- 邊跨度（Edge Span）：邊跨度是指邊所觸及的層級數減一。
- 參數化複雜性（Parameterized Complexity）：研究問題在特定參數限制下的可解性，特別是當參數較小時問題是否可以在多項式時間內解決。
- 核化（Kernelization）：一種減少問題規模的技術，通過轉換為一個等價的、規模更小的實例（核），使得核的規模與參數成函數關係。
- 樹寬（Treewidth）：圖的樹寬是其樹寬分解中的最大團的數量減一，樹寬分解是一種將圖分解為樹結構的方法。
- 平面圖（Planar Graph）：平面圖是一種可以在平面上繪製而不使邊相交的圖。
- 外平面圖（Outerplanar Graph）：外平面圖是一種特殊類型的平面圖，其中所有頂點都位於圖的外部面。
- 2-外平面圖（2-Outerplanar Graph）：2-外平面圖是一種平面圖，通過移除外部頂點可以得到一個外平面圖。
- 層級平面圖（Level Planar Graph）：層級平面圖是一種特殊類型的平面圖，其中頂點被分配到水平線上，並且邊只連接相鄰層級的頂點。
- 樹深（Treedepth）：樹深是圖的樹深分解中的最小深度，樹深分解是一種樹形結構，其中圖的每個頂點都是樹中的一個節點。