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

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

基本信息

  • 批准号:
    20500022
  • 负责人:
  • 金额:
    $ 1.33万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    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.
对于嵌入亏格为g的可定向曲面的图G的分支分解,我们给出了一个(1+2g/3)-近似算法.这个结果是基于不等式bw(G)<$(3/2)fw(G),其中bw(G)是G的分支宽度,fw(G)是G的面宽度.我们还证明了平面图的不等式bw(G)<$3gm(G),其中gm(G)是G的最大格子子式的大小,并基于这个不等式,发展了平面图分支分解的一个快速常数因子近似算法.

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
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
平面超图分支宽度的基于半径的线性时间建设性上限
Optimal branch-decomposition of planar graphs in O(n3) Time
  • DOI:
    10.1145/1367064.1367070
  • 发表时间:
    2005-07
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Q. Gu;H. Tamaki
  • 通讯作者:
    Q. Gu;H. Tamaki
Efficient reduction of vertex-disjoint Menger problem to edge-disjoint Menger problem in undirected planar graphs
无向平面图中顶点不相交门格尔问题有效简化为边不相交门格尔问题
k-Cyclic Orientations of Graphs
图的 k 循环方向
{{ 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 }}

TAMAKI Hisao其他文献

TAMAKI Hisao的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ 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)
グラフ極限を用いた大規模ネットワーク系の可制御性最大化
使用图限制最大化大规模网络系统的可控性
  • 批准号:
    24K17300
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
気象自記グラフからの時別データ生成と20世紀の東京における極端現象の長期変動分析
从天气图生成每小时数据以及 20 世纪东京极端现象的长期波动分析
  • 批准号:
    24K04404
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
幾何的グラフに対する順序構造を考慮した共通部分グラフ抽出アルゴリズム
考虑有序结构的几何图常用子图提取算法
  • 批准号:
    24K14827
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
グラフ特徴量を用いた機械学習モデルの作成
使用图特征创建机器学习模型
  • 批准号:
    24K15065
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
3つのグラフ複体と埋め込みの空間
三个复合图和嵌入的空间
  • 批准号:
    24KJ0565
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
高分子ネットワークの変形・破壊プロセスのグラフ理論を用いた研究
利用图论研究聚合物网络变形与破坏过程
  • 批准号:
    24K06898
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
応用システム指向グラフ型知識ベースのビュー構成方法に関する研究
面向应用系统的图知识库视图构建方法研究
  • 批准号:
    23K28091
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
知識グラフを用いた内容計画に基づくストーリー動画生成法の研究
基于知识图谱内容规划的故事视频生成方法研究
  • 批准号:
    23K28139
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
因果グラフ修正に基づく公平性配慮型機械学習
基于因果图修改的公平感知机器学习
  • 批准号:
    23K21700
  • 财政年份:
    2024
  • 资助金额:
    $ 1.33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了