Extending the branch-decomposition algorithm for planar graphs to broader class of graphs

将平面图的分支分解算法扩展到更广泛的图类

基本信息

  • 批准号：
    20500022
  • 负责人：
    TAMAKI Hisao
  • 金额：
    $ 1.33万
  • 依托单位：
    Meiji University
  • 依托单位国家：
    日本
  • 项目类别：
    Grant-in-Aid for Scientific Research (C)
  • 财政年份：
    2008
  • 资助国家：
    日本
  • 起止时间：
    2008 至 2010
  • 项目状态：
    已结题

项目摘要

We have developed a (1+2g/3)-approximation algorithm for the branch-decomposition of graph G embedded in an orientable surface of genus g. This result is based on an inequality bw(G)≧(3/2)fw(G), where bw(G) is the branchwidth of G and fw (G) is the face-width of G. We also have shown the inequality bw(G)≦3gm (G) for planar graphs, where gm(G) is the size of the largest grid minor of G and, based on this inequality, have developed a fast constant-factor approximation algorithm for the branch-decomposition of planar graphs.
我们已经开发了一种（1+2g/3） - 及格式算法，用于嵌入G属G属的图形G的分支分解。该结果基于不等式BW（g）≧（3/2）fw（g），其中BW（g）是G和FW（G）的分支，G（G）是G。我们也显示了不平等的BW（G）BW（G）≦3GM（G）≦3GM（G）的平面图是GM（GM）的最大gm（GM），该gm（g）的大小是GRID GRES的大小。平面图的分支分解的近似算法。

项目成果

期刊论文数量（0）
专著数量（0）
科研奖励数量（0）
会议论文数量（0）
专利数量（0）
Efficient reduction of vertex-disjoint Menger problem to edge-disjoint Menger problem in undirected planar graphs
无向平面图中顶点不相交门格尔问题有效简化为边不相交门格尔问题
Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n^<1+ε>)time
O(n^<1+ε>) 时间内平面图的分支分解和最大网格次要常数因子近似
A radius-based linear-time constructive upper bound on the branchwidth of planar hypergraphs
平面超图分支宽度的基于半径的线性时间建设性上限
Route-Enabling Graph Orientation Problems
路由启用图方向问题
  • DOI：
    10.1007/s00453-011-9589-z
  • 发表时间：
    2013
  • 期刊：
    Algorithmica
  • 影响因子：
    1.1
  • 作者：
    Takehiro Ito;Yuichiro Miyamoto;Hirotaka Ono;Hisao Tamaki;Ryuhei Uehara
  • 通讯作者：
    Ryuhei Uehara
k-cyclic orientation of graphs
图的 k 循环方向
{{ item.title }}
{{ item.translation_title }}
  • DOI：
    {{ item.doi }}
  • 发表时间：
    {{ item.publish_year }}
  • 期刊：
    {{ item.journal_name }}
  • 影响因子：
    {{ 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 }}

TAMAKI Hisao其他文献

TAMAKI Hisao的其他文献

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

{{ truncateString('TAMAKI Hisao', 18)}}的其他基金

Algorithms for width-parameters of digraphs and their applications
有向图宽度参数算法及其应用
  • 批准号：
    23500026
  • 财政年份：
    2011
  • 资助金额：
    $ 1.33万
  • 项目类别：
    Grant-in-Aid for Scientific Research (C)
Polynomial time algorithm for dualizing a monotone DNF
对偶单调 DNF 的多项式时间算法
  • 批准号：
    10680365
  • 财政年份：
    1998
  • 资助金额：
    $ 1.33万
  • 项目类别：
    Grant-in-Aid for Scientific Research (C)
Approximation algoirithms for route optimization problems : exploiting geometric structures and application to large scale problems
路线优化问题的近似算法：利用几何结构及其在大规模问题中的应用
  • 批准号：
    10205225
  • 财政年份：
    1998
  • 资助金额：
    $ 1.33万
  • 项目类别：
    Grant-in-Aid for Scientific Research on Priority Areas (B)

相似海外基金

グラフ文法に基づく推論システムによる信頼できる知識グラフの構築とその応用
基于图语法的推理系统构建可靠的知识图谱及其应用
  • 批准号：
    24K15074
  • 财政年份：
    2024
  • 资助金额：
    $ 1.33万
  • 项目类别：
    Grant-in-Aid for Scientific Research (C)
気象自記グラフからの時別データ生成と20世紀の東京における極端現象の長期変動分析
从天气图生成每小时数据以及 20 世纪东京极端现象的长期波动分析
  • 批准号：
    24K04404
  • 财政年份：
    2024
  • 资助金额：
    $ 1.33万
  • 项目类别：
    Grant-in-Aid for Scientific Research (C)
グラフ極限を用いた大規模ネットワーク系の可制御性最大化
使用图限制最大化大规模网络系统的可控性
  • 批准号：
    24K17300
  • 财政年份：
    2024
  • 资助金额：
    $ 1.33万
  • 项目类别：
    Grant-in-Aid for Early-Career Scientists
幾何的グラフに対する順序構造を考慮した共通部分グラフ抽出アルゴリズム
考虑有序结构的几何图常用子图提取算法
  • 批准号：
    24K14827
  • 财政年份：
    2024
  • 资助金额：
    $ 1.33万
  • 项目类别：
    Grant-in-Aid for Scientific Research (C)
グラフ特徴量を用いた機械学習モデルの作成
使用图特征创建机器学习模型
  • 批准号：
    24K15065
  • 财政年份：
    2024
  • 资助金额：
    $ 1.33万
  • 项目类别：
    Grant-in-Aid for Scientific Research (C)
{{ showInfoDetail.title }}

作者：{{ showInfoDetail.author }}

知道了