宮野 英次 (ミヤノ エイジ)

MIYANO Eiji

写真a

職名

教授

研究室住所

福岡県飯塚市川津680-4

研究分野・キーワード

アルゴリズム設計,計算の理論

メールアドレス

メールアドレス

ホームページ

http://algorithm.ces.kyutech.ac.jp/wp/members/miyano/

Scopus 論文情報  
総論文数: 0  総Citation: 0  h-index: 9

Citation Countは当該年に発表した論文の被引用数

出身大学 【 表示 / 非表示

  • 1991年03月   九州大学   工学部   情報工学科   卒業   日本国

出身大学院 【 表示 / 非表示

  • 1995年11月  九州大学  工学研究科  情報工学専攻  博士課程・博士後期課程  修了  日本国

  • 1993年03月  九州大学  工学研究科  情報工学専攻  修士課程・博士前期課程  修了  日本国

取得学位 【 表示 / 非表示

  • 九州大学 -  博士(工学)  1995年11月

学内職務経歴 【 表示 / 非表示

  • 2019年04月
    -
    継続中

    九州工業大学   大学院情報工学研究院   知能情報工学研究系   教授  

  • 2018年04月
    -
    2020年03月

    九州工業大学   大学院情報工学研究院   副情報工学研究院長  

  • 2016年04月
    -
    2018年03月

    九州工業大学   情報工学部   情報工学部システム創成情報工学科長  

  • 2016年04月
    -
    2018年03月

    九州工業大学   大学院情報工学研究院   情報工学研究院システム創成情報工学研究系長  

  • 2014年10月
    -
    2018年03月

    九州工業大学   理数教育支援センター   副センター長(飯塚分室長)  

全件表示 >>

学外略歴 【 表示 / 非表示

  • 2007年07月
    -
    2008年03月

    ワシントン大学   計算機科学科   客員教授   アメリカ合衆国

  • 1998年04月
    -
    2001年09月

    九州芸術工科大学芸術工学部   講師   日本国

  • 1996年05月
    -
    1998年03月

    九州大学大学院システム情報科学研究科   助手   日本国

  • 1995年12月
    -
    1996年05月

    九州大学工学部   助手   日本国

所属学会・委員会 【 表示 / 非表示

  • 2006年04月
    -
    継続中
     

    日本オペレーションズ・リサーチ学会  日本国

  • 2003年04月
    -
    継続中
     

    ACM

  • 2001年04月
    -
    継続中
     

    電子情報通信学会  日本国

  • 2001年04月
    -
    継続中
     

    情報処理学会  日本国

専門分野(科研費分類) 【 表示 / 非表示

  • 情報学基礎理論

 

論文 【 表示 / 非表示

  • Parameterized algorithms for the Happy Set problem

    Asahiro Y., Eto H., Hanaka T., Lin G., Miyano E., Terabaru I.

    Discrete Applied Mathematics    304   32 - 44   2021年12月  [査読有り]

     概要を見る

    In this paper we study the parameterized complexity for the MAXIMUM HAPPY SET problem (MaxHS): For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k, by neighborhood diversity, or by cluster deletion number.

    DOI Scopus

  • Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles

    Shu Q., Chen Y., Han S., Lin G., Miyano E., Zhang A.

    Theoretical Computer Science    882   2021年08月  [査読有り]

     概要を見る

    An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiamčik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree Δ is acyclically edge (Δ+2)-colorable. Despite many milestones, the conjecture remains open even for planar graphs. In this paper, we confirm affirmatively the conjecture on planar graphs without intersecting triangles. We do so by first showing, by discharging methods, that every planar graph without intersecting triangles must have at least one of the six specified groups of local structures, and then proving the conjecture by recoloring certain edges in each such local structure and by induction on the number of edges in the graph.

    DOI Scopus

  • Complexity and approximability of the happy set problem

    Asahiro Y., Eto H., Hanaka T., Lin G., Miyano E., Terabaru I.

    Theoretical Computer Science    868   123 - 144   2021年04月  [査読有り]

     概要を見る

    In this paper we study the approximability of the MAXIMUM HAPPY SET problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.

    DOI Scopus

  • Graph Orientation with Edge Modifications

    Asahiro Y., Jansson J., Miyano E., Ono H., Sandhya T.P.

    International Journal of Foundations of Computer Science    32 ( 2 ) 209 - 233   2021年01月  [査読有り]

     概要を見る

    The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices' resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges, H admits an orientation optimizing some objective involving the vertices' outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

    DOI Scopus

  • How to pack directed acyclic graphs into small blocks

    Asahiro Y., Furukawa T., Ikegami K., Miyano E., Yagita T.

    Discrete Applied Mathematics    288   91 - 113   2021年01月  [査読有り]

     概要を見る

    This paper studies the following variant of clustering or laying out problems for directed acyclic graphs (DAG for short), called the minimum block transfer problem. The objective of this problem is to find a partition of a node set which satisfies the following two conditions: (i) Each element (called a block) of the partition has a size that is at most B and (ii) the maximum number of external arcs among directed paths from the roots to the leaves is minimized. Here, an external arc is defined as an arc connecting two distinct blocks. This paper mainly studies the case B=2. First, we show that the problem is NP-hard even if the height of DAGs is three and its maximum indegree and outdegree are two and three, respectively. Then, we design (i) linear-time optimal algorithms for DAGs of height at most two, (ii) a very simple 2-approximation algorithm, and moreover, (iii) a (2−2∕h)-approximation algorithm for the case that the height h of the input DAG is even and the other one for odd h, whose approximation ratio is 2−2∕(h+1). As for the inapproximability of the problem, for any ε>0 and unless P = NP, we show that the problem does not admit any polynomial time (3∕2−ε)-approximation ((4∕3−ε)-approximation, resp.) algorithm if the height of the input DAGs is restricted to at most five (at least six, resp.). Also, in the case B≥3, we show the NP-hardness and prove a (3∕2−ε)-inapproximability of this case.

    DOI Scopus

全件表示 >>

口頭発表・ポスター発表等 【 表示 / 非表示

  • 最大ハッピー集合問題に対する近似アルゴリズム

    朝廣雄一,江藤宏,土中哲秀,Guohui Lin,宮野英次,寺原一平

    電子情報通信学会コンピュテーション研究会  (オンライン開催)  2020年12月  -  2020年12月    電子情報通信学会

  • 最大出次数最小グラフ有向化問題における辺重みと頂点重み

    御厨議史,朝廣雄一,Jesper Janssen,宮野英次,小野廣隆

    令和2年度OR学会九州支部・若手OR交流会  (博多バスターミナル9F第10・11ホール,福岡市)  2020年11月  -  2020年11月    日本オペレーションズリサーチ学会九州支部

  • 複製文字列長を固定したタンデム複製問題について

    西谷麻生,歌島侃勇,宮野英次

    令和2年度OR学会九州支部・若手OR交流会  (博多バスターミナル9F第10・11ホール,福岡市)  2020年11月  -  2020年11月    日本オペレーションズリサーチ学会九州支部

  • LINEにおいて人間らしい振る舞いをする雑談対話システムの構築

    川添和希,藤本晶子,宮野英次

    令和2年度OR学会九州支部・若手OR交流会  (博多バスターミナル9F第10・11ホール,福岡市)  2020年11月  -  2020年11月    日本オペレーションズリサーチ学会九州支部

  • 最大ハッピー集合問題に対する貪欲アルゴリズムの実装評価

    藤井澪央,寺原一平,宮野英次

    令和2年度OR学会九州支部・若手OR交流会  (博多バスターミナル9F第10・11ホール,福岡市)  2020年11月  -  2020年11月    日本オペレーションズリサーチ学会九州支部

全件表示 >>

科研費獲得実績 【 表示 / 非表示

  • 初期解からの変更数を制約に持つ組合せ最適化問題に対するアルゴリズム設計(代表)

    基盤研究(C)

    研究期間:  2021年04月  -  2024年03月

    研究課題番号:  21K11755

  • 組合せ最適化問題の条件強化と条件緩和に対するアルゴリズム設計(代表)

    基盤研究(C)

    研究期間:  2017年04月  -  2021年03月

    研究課題番号:  17K00016

  • グラフ構造を高度に利用した高性能グラフアルゴリズム設計(代表)

    基盤研究(C)

    研究期間:  2014年04月  -  2017年03月

    研究課題番号:  26330017

  • 離散最適化問題の計算モデルと高品質アルゴリズム設計(代表)

    基盤研究(C)

    研究期間:  2011年04月  -  2014年03月

    研究課題番号:  23500020

  • グラフ最適化問題の近似上界と近似下界の研究(代表)

    基盤研究(C)

    研究期間:  2008年04月  -  2011年03月

    研究課題番号:  20500017

全件表示 >>

その他競争的資金獲得実績 【 表示 / 非表示

  • 最適化問題の精度保証付きアルゴリズム設計(代表)

    提供機関:  文部科学省 

    研究期間:  2007年07月  -  2008年03月

 

担当授業科目 【 表示 / 非表示

  • 2020年度  離散数学Ⅱ

  • 2020年度  学際情報特別実験及び演習Ⅰ

  • 2020年度  学際情報講究Ⅰ

  • 2020年度  学際情報講究Ⅰ

  • 2020年度  学際情報特別実験及び演習Ⅰ

全件表示 >>

教育活動に関する受賞・指導学生の受賞など 【 表示 / 非表示

  • 若手OR研究交流会「優秀発表賞」

    2019年10月   日本オペレーションズリサーチ学会九州支部

  • 電子情報通信学会九州支部「学術奨励賞」

    2019年03月   電子情報通信学会九州支部

  • 若手OR研究交流会「最優秀発表賞」

    2017年10月   日本オペレーションズリサーチ学会九州支部

  • 若手OR研究交流会「最優秀発表賞」

    2016年10月   日本オペレーションズリサーチ学会九州支部

  • 若手OR研究交流会「最優秀発表賞」

    2015年10月   日本オペレーションズリサーチ学会九州支部

全件表示 >>

 

学会・委員会等活動 【 表示 / 非表示

  • 2021年01月
    -
    2021年12月

    The Ninth International Symposium on Computing and Networking (CANDAR2021)   Program Committee

  • 2020年04月
    -
    継続中

    日本オペレーションズ・リサーチ学会   九州支部・副支部長

  • 2020年01月
    -
    2020年12月

    The Eighth International Symposium on Computing and Networking (CANDAR2020)   Program Committee

  • 2019年01月
    -
    2019年12月

    21st Workshop on Advances in Parallel and Distributed Computational Models (APDCM2019)   PC member

  • 2019年01月
    -
    2019年12月

    The Seventh International Symposium on Computing and Networking (CANDAR2019)   Program Committee

全件表示 >>

社会貢献活動(講演会・出前講義等) 【 表示 / 非表示

  • 第24回九工大わくわく科学教室/STEM教育推進部門(飯塚)

    2021年03月
     
     
  • 嘉穂高校理数科課題研究発表会

    2021年02月
     
     
  • 第23回九工大わくわく科学教室/STEM教育推進部門(飯塚)

    2020年12月
     
     
  • 新宮高校プログラミングセミナー/STEM教育推進部門(飯塚)

    2020年08月
     
     

     概要を見る

    2020年8月5日~7日の3日間、福岡県立新宮高等学校理数科12名(1年生)を対象にプログラミングセミナーを実施しました。

    8月5日は本学飯塚キャンパスにおいて、『基礎プログラミング演習』としてマイクロマウスを用いた演習、『基礎プログラミング講座』としてC言語の基礎についての講義を行い、その後にオリジナルプログラム作成に向けて各班で案を出し合いました。2日目の8月6日は新宮高校に場所を移し、高校生はTA(九工大在学生)のアドバイスを受けながらオリジナルプログラムの作成に取り掛かりました。最終日の8月7日午後には研究発表会としてプレゼンテーションを行い、完成したプログラムを披露しました。

     新宮高校の皆さま、関係の皆さま、ありがとうございました。

     講師 : 篠原武 名誉教授
        大野芳久 技術専門職員
     補助 : TA 3名

  • かいたまちづくりフェスタ『サイエンス科学実験』/STEM教育推進部門(飯塚)

    2020年01月
     
     

     概要を見る

    2020年1月19日(日)、飯塚市の頴田まちづくり協議会様より依頼を受け、頴田交流センター別館多目的ホール(旧サンシャインかいた)で開催された『かいたまちづくりフェスタ』で、小田部荘司 教授(大学院情報工学研究院 物理情報工学研究系)によるサイエンス科学実験を行いました。

    実験の前半は、液体窒素を用いて、花やバナナなどを凍らせる実験を行い、超低温の様子を観察しました。
    後半は超伝導体による永久磁石の浮上実験を行いました。

    約350名収容できる会場には子どもから大人まで多くの人が集まり、次々と起こる不思議な現象に引き込まれていました。

    参加された皆さま、関係の皆さま、ありがとうございました。

    『九工大 小田部教授によるサイエンス科学実験 ~超伝導体による浮上実験~』
    講 師 : 小田部荘司 教授(大学院情報工学研究院 物理情報工学研究系)
    補 佐 : 学生 1名

全件表示 >>

 

国際会議の開催 【 表示 / 非表示

  • WAAC2008: The 11th Japan-Korea Joint Workshop on Algorithms and Computation

    2008年07月19日  -  2008年07月20日  IEICE Information and Systems Society,Technical Committee on Theoretical Foundations of Computing (COMP),the Special Interest Group on Algorithms (SIGAL) of the Information Processing Society of Japan,and Graduate School of Information Science and Electrical Engineering (ISEE),Kyushu University.