研究者詳細

教職員基本情報
氏名
Name
大月 英明 ( オオツキ ヒデアキ , OOTSUKI Hideaki )
所属
Organization
理工学部機械システム工学科
職名
Academic Title
講師
専攻分野
Area of specialization

計算機科学、近似アルゴリズム、計算量理論

学会活動
Academic societies

情報処理学会
電子情報通信学会
言語処理学会
日本統計学会
日本バーチャルリアリティ学会

著書・学術論文数
No. of books/academic articles
総数 total number (17)
著書数 books (0)
学術論文数 articles (17)

出身大学院
大学院名
Grad. School
修了課程
Courses
   Completed
修了年月(日)
Date of Completion
修了区分
Completion
   Classification
名古屋大学大学院工学研究科 博士後期課程  2005年03月  単位取得満期退学 
詳細表示
取得学位
     
学位区分
Degree
   Classification
取得学位名
Degree name
学位論文名
Title of Thesis
学位授与機関
Organization
   Conferring the Degree
取得年月(日)
Date of Acquisition
博士 博士(情報科学)  A Study of the Biclique Edge Partition and Cover Problems  名古屋大学大学院  2015年03月25日 
修士 修士  Gravitational Perturbation of Black Holes by the Newman-Penrose Formalism  弘前大学大学院理学研究科物理学専攻修士課程  1992年03月 
学士 学士    名古屋大学理学部物理学科  1989年03月 
詳細表示
研究経歴
長期研究/短期研究
Long or Short
   Term research
研究課題名
Research Topic
長期研究  様々な計算問題の計算の時間的複雑さに関して考察を行う 

概要(Abstract) 主にグラフ理論に関連する計算問題についての時間的複雑さの研究を行う 

短期研究  NP困難最適化問題の近似不可能性 

概要(Abstract) NP困難最適化問題は、多項式時間で最適解を求めることが不可能であると一般に信じられている。しかし、ある種の問題に関しては、近似アルゴリズムによって近似解を多項式時間で求めることができる。この研究では、その近似アルゴリズムの近似限界について考察することにより、NP困難最適化問題の性質についての理解を深めていく。 

詳細表示
学術論文
年度
Year
論文題目名
Title of the articles
共著区分
Collaboration
   Classification
NeoCILIUS
   請求番号/資料ID
Request No
掲載誌名 Journal name,出版機関名 Publishing organization,巻/号 Vol./no.,頁数 Page nos.,発行年月(日) Date
2021  南山大学理工学部のパブリックイメージについて  単著   
アカデミア. 理工学編 : 南山大学紀要  , 南山大学  , 22  , pp. 220 - 223  , 2022/03   

概要(Abstract)  

備考(Remarks) この論文では南山大学理工学部のパブリックイメージを Twitter のツイートから推測する.ここでは「南山大学」「理工学部」という単語を含むツイートをコーパスとして Word2Vec のモデルを作成した.Word2Vec のモデルは 2021 年 4 月 1 日から 12 月 31 日までのツイートから,「南山大学」「理工学部」の両方を含む 63694 ツイートを用いて作成した.このモデルから,いくつかの単語に類似する単語ベクトルを抽出した.この手法で得られたモデルを受験者データなどと関連させることにより,より効率的な広報などへの応用が期待できる. 

2020  Finding a Perfect Matching of a Balanced Bipartite Graph by Quantum Search Algorithm  単著   
南山大学紀要『アカデミア」理工学編  , 南山大学  , 21  , pp.1-4  , 2021/03   

概要(Abstract) Finding maximal matchings of graphs is a well-studied problem. Some deterministic algorithms solve this problem by polynomial time. We apply Grover's quantum search algorithm to nd a perfect matching of balanced bipartite graphs. We show that in some restricted cases, this problem can be solved by O(1) queries to an oracle. We investigate the dependencies of the size of the answer on the computational complexity of this problem. 

備考(Remarks)  

2020  政治的傾向とTwitter投稿の誤字との関係について  単著   
南山大学紀要『アカデミア」理工学編  , 南山大学  , 21  , pp.54 - 59  , 2021/03   

概要(Abstract) 特定の政治的傾向を持つTwitter アカウントが,誤字を含むツイートを投稿しやすいかどうかについて統計的に調査した.ここではTwitter アカウントをリベラル群と保守群にわけ,それぞれの群が特定の誤字を含むツイートを投稿する確率を推定する.この推定には,事前分布を一様分布とした事後分布を利用するベイズ統計的手法を用いた.誤字に関しては元内閣総理大臣の安倍晋三氏を「阿部首相」とするもの,百田尚樹氏の著書である「日本国紀」を「日本国記」とするものを調査した.この研究では,どちらの誤字に関してもリベラル群より保守群が誤字を投稿する確率が高いことが示された. 

備考(Remarks)  

2019  A New Polynomial-Time Solvable Graph Class for the Minimum Biclique Edge Cover Problem  単著   
IEICE TRANSACTIONS on Discrete Mathematics and Its Applications  , IEICE  , Vol.E103-A,No.10  , pp.1202-1205  , 2020/10   

概要(Abstract) The minimum biclique edge cover problem (MBECP) is NP-hard for general graphs.It is known that if we restrict an input graph to the bipartite domino-free class, MBECP can be solved within polynomial-time of input graph size.We show a new polynomial-time solvable graph class for MBECP that is characterized by three forbidden graphs, a domino, a gem and $K_4$. This graph class allows that an input graph is non-bipartite, and includes the bipartite domino-free graph class properly.
 

備考(Remarks)  

2017  2 部グラフの路重複数の計算アルゴリズム  単著   
南山大学紀要『アカデミア」理工学編  , 南山大学  , 18  , pp.38-43  , 2018/03   

概要(Abstract) 2部グラフ B=(X_B,Y_B,E_B) の路重複数 R(B) は,最小2部クリーク辺被覆問題の計算の複雑さに関係する.ここでは2部グラフ B の路重複数を計算するアルゴリズムを提案する.このアルゴリズムの計算時間は O(m \bar m^{n/2}))である.ここで m=|E_B| ,\bar m=|E_{\bar B}| ,n=|X_B| +|Y_B| である.ただし \bar B は B の補グラフである.このアルゴリズムは,グラフ B がドミノフリーであるかどうかを O(m \bar m^2) の計算時間で判定する. 

備考(Remarks)  

2016  非2重連結性遺伝2部グラフの変形ガロア束のサイズについて  単著   
Academia Sciences and Engineering  , 南山大学  , 17  , 2017/03   

概要(Abstract) 我々は一般の2 部グラフに対して変形ガロア束を定義し,距離遺伝2部グラフに対し,2 部クリーク辺被覆問題が多項式時間で解けることを示した.非2重連結性遺伝2 部グラフクラスとは,ドミノフリーグラフクラスと距離遺伝2部グラフの両方と交差するグラフクラスである.ここでは頂点数n (\geq 3) の非2重連結性遺伝2 部グラフB に対する変形ガロア束Gm(B) のサイズを評価する.具体的にはGm(B) の頂点数と辺数は,それぞれ3n/2+1 未満と5n/2-2 未満であることを示す. 

備考(Remarks)  

2014  The Biclique Cover Problem and the Modified Galois Lattice  共著   
IEICE TRANSACTIONS on Foundations of Computer Science  , IEICE  , Vol.E98-D, No.3  , pp. 497-502   , 2015/03   

概要(Abstract) The minimum biclique cover problem is known to be NP-hard for general bipartite graphs. It can be solved in polynomial time for C4-free bipartite graphs,bipartite distance hereditary graphs and bipartite domino-free graphs. In this paper, we define the modified Galois lattice $G_m(B)$ for
a bipartite graph $B$ and introduce the redundant parameter $R(B)$.We show that $R(B)=0$ if and only if $B$ is domino-free. Furthermore, for an input graph such that $R(B)=1$, we show that the minimum biclique cover problem can be solved in polynomial time. 

備考(Remarks)  

2014  A Study of the Biclique Edge Partition and Cover Problems(博士論文)  単著   
2015/03   

概要(Abstract)  

備考(Remarks) 論情科博第14号(名古屋大学) 

2012  Hardness of Approximation of Graph Partitioning into Balanced Complete Bipartite Subgraphs  単著   
南山大学 アカデミア 数理情報編  , 南山学会  , 13/1  , pp.1-11  , 2013/03   

概要(Abstract)  

備考(Remarks)  

2009  Inapproximability of the Minimum Biclique Edge Partition Problem  共著   
IEICE TRANSACTIONS on Foundations of Computer Science  , IEICE  , E93-D, No.2  , 290-292  , 2010/02   

概要(Abstract) For a graph G, a biclique edge partition SBP(G) is a collection of bicliques (complete bipartite subgraphs) Bi such that each edge of G is contained in exactly one Bi. The Minimum Biclique Edge Partition Problem (MBEPP) asks for SBP(G) with the minimum size. In this paper, we show that for arbitrary small ε>0, (6053/6052-ε)-approximation of MBEPP is NP-hard. 

備考(Remarks)  

詳細表示
研究発表
年度
Year
題目又はセッション名
Title or Name of Session
細目
Authorship
発表年月(日)
Date
発表学会等名称 Name, etc. of the conference at which the presentation is to be given, 主催者名称 Organizer, 掲載雑誌名等 Publishing Magazine,発行所 Publisher,巻/号 Vol./no.,頁数 Page nos.
2021  東京五輪報道におけるメディアリテラシーについて  単独  2022/3/20 
日本教育工学会 2022年春季全国大会  , 日本教育工学会   

概要(Abstract) 2021年7月に開催された東京オリンピック・パラリンピックは、開催を反対する世論の中、計画通り終了した。本来は2020年に開催される予定であった本大会は、2021年に延期され開催されたものであるが、開催に至るまで不祥事とされる報道が重なった大会でもあった。それらの報道の中には、不正確な報道、本大会の開催を阻止したいという動機で恣意的にねじ曲げられた報道も見受けられた。その中で、五輪開会式担当者に対する報道の問題点を指摘する。そしてこの際の報道に見られたような誤情報を広めない為のメディアリテラシー養成の必要性を考察する。 

備考(Remarks)  

2018  最小2部クリーク辺被覆問題が多項式時間で解ける新しいグラフクラス  単独  2019/03 
情報処理学会第81回全国大会  , 情報処理学会   

概要(Abstract) 一般に最小 2 部クリーク辺被覆問題は NP-困難である.一方、2 部グラフ B に対して,路重複数 R(B) がR(B) ≤ 1 であれば,その最小 2 部クリーク辺被覆問題は多項式時間で解けることがわかっている.ここではグラフ G が 2 部グラフでない場合でも,その誘導部分グラフとして、ドミノ,K4,そして端点を共有する 2 本のコードが存在する C5 のいずれも含まない場合,その最小 2 部クリーク辺被覆問題は多項式時間で解けることを示す.
 

備考(Remarks)  

2015  距離遺伝2部グラフの変形ガロア束のサイズについて  共同  2016/03/06 
第157回アルゴリズム研究会  , 情報処理学会 アルゴリズム研究会  , AL-157   

概要(Abstract)  

備考(Remarks)  

2013  2部クリーク被覆と modified Galois lattice  共同  2014/03/03 
第147回アルゴリズム研究会  , 情報処理学会 アルゴリズム研究会  , AL-147   

概要(Abstract)  

備考(Remarks)  

2010  Inapproximability of The Biclique Partition Problem  共同  2010/11 
The China-Japan Joint Conference on Computational Geometry, Graphs and Applications 2010  , CGGA2010   

概要(Abstract)  

備考(Remarks)  

2009  集合基底問題の正規基底を求めるヒューリスティックアルゴリズム  共同  2010/1 
第128回アルゴリズム研究会  , 情報処理学会 アルゴリズム研究会  , AL-128   

概要(Abstract)  

備考(Remarks)  

2005  辺縮約問題の近似困難性  共同  2005/09 
第4回情報科学技術フォーラム  , FIT 2005   

概要(Abstract)  

備考(Remarks)  

2005  Inapproximability of the edge contraction problem  共同  2005/08 
2005 Japan-Korea Joint Workshop on Algorithms and Computation   

概要(Abstract)  

備考(Remarks)  

2003  MIN 3-SET COVER の近似困難性  共同  2003/11 
第92回アルゴリズム研究会  , 情報処理学会  , AL-92  , 55   

概要(Abstract)  

備考(Remarks)  

詳細表示
研究助成
年度
Year
助成名称または科学研究費補助金研究種目名
Name of grant or research classification for scientific research funding
研究題目
Research Title
役割(代表/非代表)
Role
助成団体
Granting body
助成金額
Grant amount
2006  南山大学パッヘ研究奨励金 I −A−2  NP困難な最適化問題の近似不可能性についての研究 
     

研究内容(Research Content) 研究助成 

備考(Remarks)  

2005  南山大学パッヘ研究奨励金 I −A−2  NP困難な最適化問題の近似不可能性についての研究 
     

研究内容(Research Content) 研究助成 

備考(Remarks)  

1992  日本学術振興会特別研究員DC1  重力波シミュレーション、及び数値的相対論の解析 
  日本学術振興会   

研究内容(Research Content) 研究奨励金 

備考(Remarks)  

詳細表示
教育活動
年度
Year
タイトル
Title
内容等
Content
活動期間
Period of Activities
2020  教材作成 

2020年度Q4プログラミング応用電子資料の一部分を作成 

 
2020  教材作成 

2020年度Q3プログラミング応用電子資料の一部分を作成 

 
2019  教材作成 

2019年度Q4プログラミング応用電子資料の一部分を作成 

 
2019  教材作成 

2019年度Q3プログラミング応用電子資料の一部分を作成 

 
2018  教材作成 

2018年度Q4プログラミング応用電子資料の一部分を作成 

 
2018  教材作成 

2018年度Q3プログラミング基礎電子資料の一部分を作成 

 
2016  教材作成 

2016年度春学期プログラミング応用実習電子資料の一部分を作成 

 
2016  教材作成 

2016年度春学期基礎演習電子資料の一部分を作成 

 
2016  教材作成 

2016年度秋学期プログラミング基礎実習電子資料の一部分を作成 

 
2015  教材作成 

2015年度春学期プログラミング応用実習電子資料の一部分を作成 

 
詳細表示
著書・学術論文に関する統計情報
年度
Academic Year
学術研究著書の件数
No. of Academic Books
学会誌・国際会議議事録等に掲載された学術論文の件数
No. of Academic Articles in Journals/Int'l Conference Papers
学内的な紀要等に掲載された学術論文の件数
No. of Academic Articles Pub'd in University Bulletins
学会受賞等の受賞件数
No. of Academic Awards Received
国際学会でのゲストスピーカーの件数
No. of Times as Guest Speaker at Int'l Academic Conferences
国際学会での研究発表の件数
No. of Presentations of Papers at Int'l Academic Conferences
国内学会でのゲストスピーカーの件数
No. of Times as Guest Speaker at National Academic Conf.
国内学会での研究発表の件数
No. of Papers Presented at National Academic Conf.
2021 
2020 
2019 
2018 
2017 
2016 
2015 
2014 
2013 
2012 
詳細表示

2022/04/25 更新