グラフ上の辺素パスに関する最適化問題の研究

图上边不相交路径优化问题研究

基本信息

  • 批准号:
    07J01958
  • 负责人:
  • 金额:
    $ 1.73万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
  • 财政年份:
    2007
  • 资助国家:
    日本
  • 起止时间:
    2007 至 2009
  • 项目状态:
    已结题

项目摘要

本年度の研究の主な成果は,以下の3点に分類される.(1)点素パスに関する最適化問題点素(辺素)パスに関する最適化問題は,これまで自明なケース以外には多項式時間アルゴリズムが知られていなかったが,2008年にColin de Verdiere & Schrijverによって非自明なケースに対する多項式時間アルゴリズムが与えられた.そこで本年度の研究では,彼らの結果を他のケースに拡張し,平面グラフ上の問題で頂点対の数が少ないときの多くの非自明なケースに対するアルゴリズムを構築した.(2)辺素パス問題のアルゴリズム辺素(点素)パス問題に対しては,Robertson & Seymourによる多項式時間解法が知られているが,その正当性の証明は非常に難解であり,一般化した問題を扱う際の大きな障害となっている.また,彼らのアルゴリズムには,計算時間の中に頂点対数に依存した非常に大きな係数がかかってくる,という問題点がある.そこで本研究では,グラフに4辺連結性やオイラー性を仮定して,辺素パス問題に対するより単純で高速なアルゴリズムを与えた.(3)マトロイド構造を利用したアルゴリズムマトロイドの一般化として導入されたジャンプシステムや,その上で定義される離散凸関数は数多くの効率的に解ける組合せ最適化問題を含む枠組みである.本研究では,いくつかの具体的な組合せ最適化問題が,これらの構造の一般論を用いることで解けることを示した.特に,ジャンプシステムの理論を用いて,今まで多項式時間解法が知られていなかった(n-3)-連結度増大問題に対する初めての多項式時間解法を与えた.この成果は,個々の問題に対するアルゴリズムを構築する際に,ジャンプシステムや離散凸関数の理論が利用できることを明らかにしており,他の未解決の組合せ最適化問題に対する応用が期待される.
The main results of this year's research are classified as follows: (1)In 2008, Colin de Verdiere & Schrijver published a paper on the optimization problem of dot elements. This year's research results show that the number of vertex pairs on the plane is less than the number of vertex pairs on the plane, and the number of vertex pairs on the plane is more than the number of vertex pairs on the plane. (2)Robertson & Seymour's polynomial time solution is known, and the justification of the problem is very difficult. In addition, the calculation time of the vertex pairs depends on the very large coefficients of the problem points. This study is aimed at solving the problem of high speed and high efficiency. (3)The structure of a discrete convex function is used to generalize and introduce a discrete convex function into a combinatorial optimization problem. In this paper, we study the concrete combinatorial optimization problem. In particular, the polynomial time solution to the problem of (n-3)-connectivity increase is proposed. The results of this work are expected to be useful for solving unsolved combinatorial optimization problems.

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Cone superadditivity of discrete convex functions
离散凸函数的锥超可加性
  • DOI:
    10.1007/s10107-011-0447-1
  • 发表时间:
    2012
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Y. Kobayashi;K. Murota and R. Weismantel
  • 通讯作者:
    K. Murota and R. Weismantel
The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
欧拉图和四边连通图中的边不相交路径问题
  • DOI:
    10.1007/s00493-014-2828-6
  • 发表时间:
    2015
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    監修:浅野美智恵;分担著者名:只浦寛子;Ken-ichi Kawarabayashi and Yusuke Kobayashi
  • 通讯作者:
    Ken-ichi Kawarabayashi and Yusuke Kobayashi
A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs
一种在次三次图中查找最大无三角形 2 匹配的简单算法
  • DOI:
  • 发表时间:
    2010
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    鈴木智裕;水野鉄浩;国方淳;佐藤宏司;浅沼博;美濃島薫;平等拓範;Y.Kobayashi
  • 通讯作者:
    Y.Kobayashi
Operations on M-convex Functions on Jump Systems
跳跃系统上 M 凸函数的运算
The Induced Disjoint Paths Problem
  • DOI:
    10.1007/978-3-540-68891-4_4
  • 发表时间:
    2008-05
  • 期刊:
  • 影响因子:
    0
  • 作者:
    K. Kawarabayashi;Yusuke Kobayashi
  • 通讯作者:
    K. Kawarabayashi;Yusuke Kobayashi
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

小林 佑輔其他文献

需給ネットワーク分割問題における供給率最大化アルゴリズム
供需网络划分问题的供应率最大化算法
  • DOI:
  • 发表时间:
    2017
  • 期刊:
  • 影响因子:
    0
  • 作者:
    高山 功輝;小林 佑輔
  • 通讯作者:
    小林 佑輔
Finding a Zero Path in Z_3-Labeled Graphs
在 Z_3 标记图中查找零路径
  • DOI:
  • 发表时间:
    2014
  • 期刊:
  • 影响因子:
    0
  • 作者:
    河瀬 康志;小林 佑輔;山口 勇太郎
  • 通讯作者:
    山口 勇太郎
Z_3ラベル付きグラフにおける指定ラベルs-tパスの発見
在 Z_3 标记图中查找指定的标记 s-t 路径
  • DOI:
  • 发表时间:
    2014
  • 期刊:
  • 影响因子:
    0
  • 作者:
    河瀬 康志;小林 佑輔;山口 勇太郎
  • 通讯作者:
    山口 勇太郎
Packing disjoint A-paths with fixed length
打包具有固定长度的不相交 A 路径
  • DOI:
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Remy Belmonte;土中 哲秀;神崎 勝彰;清見 礼;小林 靖明;小林 佑輔;Michael Lampis ;小野 廣隆;大舘 陽太
  • 通讯作者:
    大舘 陽太
最大連結カットに対するパラメータ化アルゴリズム
最大连通割的参数化算法
  • DOI:
  • 发表时间:
    2019
  • 期刊:
  • 影响因子:
    0
  • 作者:
    江藤 宏;土中 哲秀;小林 靖明;小林 佑輔
  • 通讯作者:
    小林 佑輔

小林 佑輔的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('小林 佑輔', 18)}}的其他基金

多面体的手法と離散構造を用いた組合せ最適化問題の解法
使用多面体方法和离散结构解决组合优化问题
  • 批准号:
    24K02901
  • 财政年份:
    2024
  • 资助金额:
    $ 1.73万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
組合せ最適化における多面体手法の高度化
组合优化中多面体方法的复杂性
  • 批准号:
    20K11692
  • 财政年份:
    2020
  • 资助金额:
    $ 1.73万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了