New Graph Calculi for Planar Non-3-Colorable Graphs
スポンサーリンク
概要
- 論文の詳細を見る
The Hajós calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP=co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.
- （社）電子情報通信学会の論文
- 2008-09-01
著者
-
堀山 貴史
京都大学大学院情報学研究科
-
堀山 貴史
埼玉大学情報システム工学科
-
Tamaki Suguru
Graduate School Of Informatics Kyoto University
-
堀山 貴史
埼玉大学
-
Iwama Kazuo
Graduate School Of Informatics Kyoto University
-
HANATANI Yoichi
Graduate School of Informatics, Kyoto University
-
HORIYAMA Takashi
Graduate School of Science and Engineering, Saitama University
-
Hanatani Yoichi
Graduate School Of Informatics Kyoto University
-
HORIYAMA Takashi
Saitama University
-
Horiyama Takashi
Graduate School Of Informatics Kyoto University
-
Horiyama Takashi
Graduate School Of Engineering Kyoto University
-
IWAMA Kazuo
Graduate School of Informatics, Kyoto University
関連論文
- DS-1-14 飛び道具を考慮した逆算法に基づく詰将棋列挙技術(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- 逆算法に基づく詰将棋の列挙
- D-1-7 逆算法に基づく詰将棋の列挙(D-1. コンピュテーション)
- Automatic clock gating generation through power-optimal control signal selection (VLSI設計技術)
- 二分決定グラフ上での知識表現および正/ホーン関数の認識問題
- 複数の二分決定グラフを用いたNP完全な組合せ問題の解法
- 正4面体と他の正多面体との共通の辺展開図に関する研究
- 自動クロックゲーティング生成における電力最適化制御信号選択手法
- 秘密分散を用いた安全なVickreyオークション
- 論理関数の畳み込み機構を導入した省面積FPGAの実現と評価
- 8C45 ことばによる手話単語の記述と三次元表現
- A (2-c(logN)/N)-Approximation Algorithm for the Stable Marriage Problem(Invited Papers from New Horizons in Computing)
- 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化(検証・理論, 組込技術とネットワークに関するワークショップ)
- 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化
- 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化(検証・理論, 組込技術とネットワークに関するワークショップ)
- 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化
- C言語を用いた音声認識・学習LSIの設計と実現について
- C言語を用いた音声認識・学習LSIの設計と実現について
- C言語を用いた音声認識・学習LSIの設計と実現について
- A-3-13 学習回路インターフェースを持ち不特定話者に対応できる音声認識回路
- マルチステージクロックゲーテイングにおけるクロック制御回路の共有について(低電力設計,デザインガイア2010-VLSI設計の新しい大地-)
- マルチステージクロックゲーティングにおけるクロック制御回路の共有について(低電力設計,デザインガイア2010-VLSI設計の新しい大地-)
- 1-D-5 最長路問題と最大経路差問題 : その解法とJR大都市近郊区間大回りへの応用(離散・組合せ最適化(2))
- Efficient Methods for Determining DNA Probe Orders(Discrete Mathematics and Its Applications)
- New Graph Calculi for Planar Non-3-Colorable Graphs
- The Planar Hajos Calculus for Bounded Degree Graphs
- DS-1-4 Enumerating Non-3-colorable Planar Graphs by the Hajos Calculus
- オンライン問題の競合比解析の自動化について
- General Bounds for Quantum Biased Oracles (特集:量子計算と量子情報)
- オンライン問題の競合比解析の自動化について (計算機科学基礎理論の新展開)
- 平面グラフにおけるHajos Calculusの複雑さについて
- 二段組合せ回路の最大動作率について(計算理論とアルゴリズムの新展開)
- 入札額の範囲が制限された正直なオークション
- 入札額の範囲が制限された正直なオークション
- Hajos Calculus on Planar Graphs (Theoretical Computer Science and its Applications)
- 論理式の解密度の濃縮
- 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)
- 上位からの時差入力下での最適並列加算器
- 除算を表現する二分決定グラフの指数下界
- 抽象解釈手法に基づく変数の相互関係解析とそのデータパス最適化への応用(システム設計及び一般)
- 抽象解釈手法に基づく変数の相互関係解析とそのデータパス最適化への応用(システム設計および一般)
- 論理関数の畳み込み機構を導入した省面積FPGAの実現と評価
- 論理関数の畳み込み機構を導入した省面積FPGAの実現と評価(FPGAとその応用及び一般)
- A-3-25 論理関数の重ね合わせに基づく加減算向きLUT
- A-3-4 リング発振器を用いたオンチップ高速シリアル通信方式
- A-3-11 冗長2進CORDIC演算器を有する16ビットパイプラインプロセッサ
- Fine-Grained Power Gating Based on the Controlling Value of Logic Elements
- Fine-grained power gating based on the controlling value of logic gates (VLSI設計技術)
- Fine-grained power gating based on the controlling value of logic gates (システムLSI設計技術)
- Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
- Look Up Table Compaction Based on Folding of Logic Functions(Special Section on VLSI Design and CAD Algorithms)
- Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations(Discrete Mathematics and Its Applications)
- Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique(System Level Design,VLSI Design and CAD Algorithms)
- DS-1-7 いかなる辺展開でも正多面体は重ならない(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- いかなる辺展開でも正多面体は重なりを持たない (計算機科学とアルゴリズムの数理的基礎とその応用)
- 正4面体と正6面体との共通の展開図の構成に関する研究
- 正多面体の展開図における最小/最大の直径、幅および包囲長方形について
- Power Optimization of Sequential Circuits Using Switching Activity Based Clock Gating
- Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
- いかなる辺展開でも正多面体は重なりを持たない
- 正多面体の展開図における最小/最大の直径、幅および包囲長方形について
- 任意の凸多面体は重なりのない展開図に展開できるだろうか?
- 2-K-10 p6タイリング可能なポリアモンドの生成(ワークショップ「娯楽のOR-エンターテイメントの数理」)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- アスペクト比を固定した最小の周囲長方形について (アルゴリズムと計算理論の新展開)
- Automatic Multi-Stage Clock Gating Optimization Using ILP Formulation
- 多面体の非同型な展開図の個数について
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
- トロミノ詰込問題の計算複雑さについて
- General Bounds for Quantum Biased Oracles
- pmg タイリング可能なポリオミノの列挙
- A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis