Computing directed pathwidth in <i>O</i>(1.89<i>ⁿ</i>) time

スポンサーリンク

概要

• 論文の詳細を見る

• We give an algorithm for computing the directed pathwidth of a digraph with n vertices in O(1.89n) time. This is the first algorithm with running time better than the straightforward O*(2n). As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in O(1.9657n) time.

• 2012-09-27

著者

• 玉木 久夫

  明治大学

• 玉木 久夫

  明治大学理工学部情報科学科

• 玉木 久夫

  明治大学理工学部

• 玉木 久夫

  日本アイ・ビー・エム 東京基礎研

• Hisao Tamaki

  Meiji University

• Tamaki H

  Department Of Computer Science Faculty Of Science And Engineering Meiji University

• Tamaki Hisao

  Tokyo Research Laboratory Ibm Japan

• Tamaki Hisao

  The School Of Science And Technology Meiji University

• Tamaki Hisao

  Department Of Computer Science Meiji University

• Yasuaki Kobayashi

  Graduate School Of Science And Technology Meiji University.

• Keita Komuro

  Meiji University

• Toshihiro Tano

  Meiji University

• Kenta Kitsunai

  Meiji University

• Yasuaki Kobayashi

  Meiji University

関連論文

• 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
• 点集合の距離重複度列のノルムと最大部分集合問題
• 密な部分グラフ問題の貪欲解法
• 放物線のアレンジメントの組合せ複雑度について
• 平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けて
• 頂点彩色問題に対する列生成法アプローチの高速化
• テストパターンの静的圧縮における厳密解と貧欲解の比較(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
• 平面ユークリッドTSPの分割統治法ヒューリスティツクス
• 平面グラフの分枝幅決定アルゴリズムの効率的実装
• グラフ及び領域空間に関する大域丸めの幾何学的性質について
• 合成数のAKS witnessに関する実験的研究
• 小さな碁盤における囲碁の厳密解アルゴリズム
• TD-1-12 アルゴリズムデモ発見的動的計画法 : 巡回セールスマン問題を例として
• ハイパーキューブ上の順列の同形を反復しない網羅的生成
• 平面巡回セールスマン問題に対するアローラの近似アルゴリズムの効率的実装
• Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm)
• 障害物との交差数が少ない全域木
• パラメトリックなポリマトロイドとその幾何学的応用
• 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
• 巡回カメラマン問題とその自動光学的検査への応用
• 教育を目的としたC言語ソース管理APIの作成とその応用(e-learning/一般)
• JavaのeラーニングのためのEclipseプラグインの開発(e-learning/一般)
• 極小横断列挙のメモリ効率の良いアルゴリズム
• 2H-7 耐故障トーラス構成の一方式とシミュレーションによる評価
• Voronoi Diagrams with Respect to Criteria on Vision Information
• 単一根有向グラフと対称変換に基づいた囲碁の棋譜管理・閲覧システムの開発(セッション(1) : ゲーム情報学(1))
• 単一根有向グラフと対称変換に基づいた囲碁の棋譜管理・閲覧システムの開発 (人工知能基礎論研究会(第55回)特集「エンタテイメントコンピューティングの基礎と応用」および一般) -- (セッション(1)ゲーム情報学(1))
• 巡回セールスマン問題の近似アルゴリズム:天才アローラによる20年ぶりの急進展(近似アルゴリズムに関する最近の話題)
• 経路最適化問題の近似アルゴリズム : 幾何学的/非幾何学的場合の対比
• ハイパーキューブ上の単距離置換のルーティング
• 組合せ的解析における確率的手法
• Graph Orientation Problems for Multiple st-Reachability
• k-cyclic Orientations of Graphs
• グラフの自動描画における交差を考慮した巨大近傍探索
• Special Section on Discrete Mathematics and Its Applications
• Routing a Permutation in the Hypercube by Two Sets of Edge-Disjoint Paths
• Edge-Disjoint Routing in the Undirected Hypercube
• Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
• Approximation Algorithms for Geometric Optimization Problems(Special Issue on Algorithm Engineering : Surveys)
• Computing directed pathwidth in O(1.89n) time
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• A Linear Edge Kernel for Two-Layer Crossing Minimization
• Search space reduction through commitments in pathwidth computation: an experimental study

もっと見る 閉じる

スポンサーリンク