戸田 誠之助 TODA Seinosuke

ID:1000090172163

日本大学文理学部情報システム解析学科 Dept. of Computer Science and System Analysis College of Humanities and Sciences, Nihon University (2007年 CiNii収録論文より)

Search authors sharing the same name

Articles:  1-20 of 26

  • 1 / 2
  • A dynamic programmming algorithm for computing automorphism groups of a given set of matrices  [in Japanese]

    TODA Seinosuke

    X=(U_1∪U_2∪・・・∪U_m∪V,E)を適当なm+1部グラフとする.ただし,U_iとU_jの間には辺は存在しないものとする.その一方で,各辺は適当な全順序集合の要素をラベルとして持ってもよいとする.本稿では,各部集合U_iおよびVを(集合として)固定し,かつ,各辺のラべルを保存するようなXの自己同型群を求める問題を考える.この問題は一般にGl-完全である.従って,現状では,この問題に対して …

    IEICE technical report 107(73), 35-42, 2007-05-25

    References (9)

  • Extraction of temporal relation by the creation of historical natural disaster archive  [in Japanese]

    吉岡 卓 , 谷 聖一 , 戸田 誠之助

    じんもんこん2006論文集 2006, 271-278, 2006-12-14

    IPSJ 

  • Temporal reasoning system for the digital library of theater literature  [in Japanese]

    吉岡 卓 , 森井 マスミ , 谷 聖一 , 紅野 謙介 , 戸田 誠之助

    じんもんこん2006論文集 2006, 109-116, 2006-12-14

    IPSJ 

  • A simple algorithm for testing isomorphism of chordal graphs  [in Japanese]

    TODA Seinosuke

    以前の研究[IEICE Technical Report, COMP 2005-24]において、コーダルグラフの自己同型群を求めるためのアルゴリズムを設計した。また、そのアルゴリズムを利用することによって同型性も判定できることを示した。一方、そのアルゴリズムは群論的手法を多用しており、複雑で時間量の正確な解析も困難であった。そのため、群論的手法を使用することのない、より単純なアルゴリズムを設計でき …

    IEICE technical report 106(29), 57-62, 2006-04-19

    References (9)

  • Computing automorphism groups of chordal graphs whose simplicial components are of small size (Preliminary Note)

    TODA Seinosuke

    任意のコーダルグラフは単体成分と呼ばれる部分グラフに一意的に分解されることが知られている。本研究では、この事実に注目することによって、任意のコーダルグラフGに対して、Gの自己同型群がO((c!・n)^<O(1)>)時間で計算可能なことを示す。ここで、cはGの単体成分の最大サイズを表し、nはGの頂点数を表す。

    IEICE technical report. Theoretical foundations of Computing 105(144), 37-42, 2005-06-17

    References (8)

  • A Polynomial-Time Algorithm for Counting Graph Isomorphisms among Partial k-trees  [in Japanese]

    NAGOYA Takayuki , TANI Seiichi , TODA Seinosuke

    本論文では,二つのpartial k-tree G,Hと,Gの誘導部分グラフからHの誘導部分グラフへの同型写像ψが与えられたとき,GからHへのψに矛盾しない同型写像の数を数え上げるための0(Q(n,k)+n^<k+4>)時間アルゴリズムを示す.

    The Transactions of the Institute of Electronics,Information and Communication Engineers. 85(5), 424-435, 2002-05-01

    References (12)

  • Computational Complexity of Graph Isomorphism Problem  [in Japanese]

    TODA Seinosuke

    本稿では,グラフ同型性判定問題の計算量に関する研究動向を概説する.まず,この判定問題がNP困難ではないと予想させる二つの基本的な根拠を説明し,次に,グラフの様々なクラスに関する同型性判定問題の計算量について解説する.なお,本稿は文献[戸田,グラフ同型性判定問題の計算量,電子情報通信学科論文誌D-I,2002年2月掲載予定]から抜粋したものである.より詳しい内容については,この文献かまたは文献[戸田 …

    IEICE technical report. Theoretical foundations of Computing 101(708), 15-24, 2002-03-05

    References (66) Cited by (1)

  • Completeness of Graph Isomorphism Problem for Bipartite Graph Classes

    NAGOYA Takayuki , UEHARA Ryuhei , TODA Seinosuke

    2部グラフに対するグラフ同型性判定問題がGI完全であることは良く知られている。一方,2部グラフの部分クラスであるconbex graphに対しては,グラフ同型性判定問題が多項式時間で解ける。chordal bipertite graphは2部グラフの部分クラスであり,かつconvex graphを含むグラフクラスである。このクラスに対する同型性判定問題の計算量については今まで知られていなかった。本 …

    IEICE technical report. Theoretical foundations of Computing 101(708), 1-5, 2002-03-05

    References (9)

  • Computational Complexity of Graph Isomorphism Problem  [in Japanese]

    TODA Seinosuke

    本論文では,グラフ同型性判定問題の計算量に関してこれまでの研究動向を解説する.まず,この判定問題がNP困難ではないと予想させる二つの基本的な根拠を説明する.次に,グラフの様々なクラスに関する同型性判定問題の計算量について解説する.最後に,多項式時間アルゴリズムの典型として,Luksによって設計された3次グラフに対する同型性判定アルゴリズムと,名古屋によって設計されたchordalグラフに対する同型 …

    The Transactions of the Institute of Electronics,Information and Communication Engineers. 85(2), 100-115, 2002-02-01

    References (64) Cited by (1)

  • グラフ同型写像の数え上げ問題に対するアルゴリズムについて  [in Japanese]

    名古屋 孝幸 , 谷 聖一 , 戸田 誠之助

    Annual reports of the Institute of Information Sciences (1), 59-69, 2001-01

  • Computational Complexity of Counting Problems  [in Japanese]

    TODA Seinosuke

    IPSJ Magazine 40(3), 276-279, 1999-03-15

    IPSJ  Cited by (1)

  • A Polynomial-Time Algorithm for Counting Graph Isomorphisms among Partial k-trees  [in Japanese]

    NAGOYA Takayuki , TANI Seiichi , TODA Seinosuke

    本論文では、2つのpartial k-tree G, Hと、GからHへの部分同型写像ψが与えられたとき、GからHへのψに矛盾しない同型写像の数を求めるための多項式時間アルゴリズムを示す。また、M.R.Jerrum, L.G.Valiant, V.V.Vazirani〔Theoretical Computer Science, 43:169-188, 1986〕は、self-reducibleな問題 …

    IEICE technical report. Theoretical foundations of Computing 98(186), 25-33, 1998-07-23

    References (3) Cited by (2)

  • On the computational complexity of graph accessibility problem  [in Japanese]

    TARUI Jun , TODA Seinosuke

    無向グラフならびに有向グラフの到着可能性判定問題(各々を, UGAPおよびGAPと略す)は, 1970年代から研究されている古い問題であるが, 領域量が限定された計算過程を具体的な計算問題という形に表現し直したものであり, 領域量に関わる計算量理論にとっては中心的な問題である.本稿ではまず, 無向グラフのパス幅をpw(G)で表すとき, UGAPが決定性O(pw(G)^2logn)領域で判定可能であ …

    IEICE technical report. Theoretical foundations of Computing 98(186), 17-24, 1998-07-23

    References (6)

  • On the power of computation structures involved in counting problmes  [in Japanese]

    TODA Seinosuke

    本稿では, 数え上げ問題に内在する計算構造が強力な計算能力を持っていることを述べる.このことを端的に示す事実として, 適当な論理回路Cと適当な多項式p(n)ならびに存在記号と全称記号の有限回の組み合せを用いて, ψ(x^^→)≡∃_py^^→_1∀_py^^→_2・・・∃_py^^→_<k-1>∀_py^^→_kC(x^^→, y^^→_1, y^^→_2, ・・・, y^^→_< …

    IEICE technical report. Theoretical foundations of Computing 98(186), 1-7, 1998-07-23

    References (9)

  • On the power of computation structures involved in counting problmes  [in Japanese]

    TODA Seinosuke

    本稿では,数え上げ問題に内在する計算構造が強力な計算能力を持っていることを述べる.このことを端的に示す事実として,適当な論理回路Cと適当な多項式p(n)ならびに存在記号と全称記号の有限回の組み合わせを用いて,ψ(x^^→)≡∃_p<Y1>^^^→∀_p<y2>^^^→・・・∃_p<Yk>^^^→__1∀_p<Yk>^^^→C(x^^→ Y^^→_1 …

    IPSJ SIG Notes 1998(62(1998-AL-063)), 65-71, 1998-07-22

    IPSJ  References (9)

  • 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)  [in Japanese]

    Tarui Jun , Toda Seinosuke

    RIMS Kokyuroku (1041), 79-86, 1998-04

    IR 

  • Complexity Analysis of Boolean Functions via Regular Languages : Some observations on M-Programs over Groups

    TODA Seinosuke

    文献[Bar89]において,Barringtonは,段数dの任意の論理回路が5次の交代群の上で動作する長さ4^dのモノイドプログラムによって模倣できることを示した.さらに,この結果の拡張として,任意の非可解群Gに対しても同様の結果が成り立つことを示している.ただし,このときのモノイドプログラムの長さは4^dではなく,(4|G|)^dになっている.本稿では,任意の非可解群についても5次の交代群の場合 …

    IEICE technical report. Theoretical foundations of Computing 97(83), 89-93, 1997-05-30

    References (6)

  • Some Observations on an algorithm recognizing interval graphs  [in Japanese]

    NAGOYA Takayuki , TODA Seinosuke

    区間グラフの認識アルゴリズムの初期のものは、少なくともO(n^3)時間を必要とした。線形アルゴリズムとして最初のものは、BoothとLeuker [JCSS,13,1976]により開発された。しかしそのアルゴリズムはPQ-treeという特殊なデータ構造を用いていたため、非常に複雑だった。そこでKorteとMoring[SIAM J.Comput.,18:68-81,1989]は、その複雑さを緩和す …

    IEICE technical report. Theoretical foundations of Computing 97(32), 57-64, 1997-04-25

    References (6)

  • Structural Analysis of Circuit Complexity Classes by means of Monoid Programs  [in Japanese]

    Toda Seinousuke

    論理回路に基づいて定義された様々な計算量クラスがモノイドプログラムと呼ばれる計算モデルを通して代数的に特徴付けられている.モノイドプログラムの研究は端緒についたばかりであり十分な成果が上がっているとはいい難いが,回路計算量(サイズや段数)を分析するための新たな方向を提示していると思われる.本稿では,モノイドプログラムに関連した論理回路計算量クラスに関する既知の結果と未解決の諸問題を解説する.

    Proceedings of the IEICE General Conference 1996年.情報・システム(1), 359-360, 1996-03-11

  • 1 / 2
Page Top