研究者詳細

学術論文
分割表示   全件表示 >>

13 件中 1 - 10 件目

年度
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) 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)  

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)  

Page: [<<PREV] [1] [2] [NEXT>>]