研究者詳細

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

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

学会活動
Academic societies

情報処理学会
電子情報通信学会
ACM
日本統計学会
APS

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

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

概要(Abstract)  

備考(Remarks)  

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

概要(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/3   

概要(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)  

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

概要(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/2   

概要(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)  

2006  Inapproximability of the Edge-Contraction Problem  共著   
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  , IEICE  , E89-A, No.5  , 1425-1427  , 2006/05   

概要(Abstract) For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components. 

備考(Remarks)  

2005  The distribution of bequests in Japan  共著   
Journal of the Japanese and International Economies  , Elsevier  , 20  , 77-86  , 2006/03   

概要(Abstract)  

備考(Remarks)  

2005  辺縮約問題の近似困難性  共著   
情報科学技術レターズ  , 情報処理学会/電子情報通信学会  , 4  , 17-20  , 2005/09   

概要(Abstract)  

備考(Remarks)  

2002  最適化問題における近似不可能性  単著   
名古屋聖霊短期大学紀要  , 名古屋聖霊短期大学  , 23  , 31  , 2002/12   

概要(Abstract)  

備考(Remarks)  

1997  家計の保有資産の増加と貯蓄率の将来推計  共著   
季刊家計経済報告  , 家計経済研究所  , 36  , 10  , 1997/10   

概要(Abstract)  

備考(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.
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
2016  教材作成 

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

 
2016  教材作成 

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

 
2016  教材作成 

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

 
2015  教材作成 

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

 
2015  教材作成 

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

 
2015  教材作成 

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

 
2014  教材作成 

2014年度春学期プログラミング応用実習電子資料の一部分を作成.中間試験作成 

 
2014  教材作成 

2014年度秋学期プログラミング基礎実習電子資料の一部分を作成.中間試験作成 

 
2013  教材作成 

2013年度春学期プログラミング応用実習電子資料の一部分を作成.中間試験作成 

 
2013  教材作成 

2013年度秋学期プログラミング基礎実習電子資料の一部分を作成.中間試験作成 

 
詳細表示
著書・学術論文に関する統計情報
年度
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.
2017 
2016 
2015 
2014 
2013 
2012 
2011 
2010 
2009 
2008 
詳細表示

2018/09/06 更新