文献

J-GLOBAL ID：202002285227691808   整理番号：20A0425899

位相的マイナー埋め込みの陰的列挙と平面サブグラフ列挙への応用【JST・京大機械翻訳】

Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration

著者 (4件)： Nakahata Yu (Kyoto University, Kyoto, Japan) ,  Kawahara Jun (Kyoto University, Kyoto, Japan) ,  Horiyama Takashi (Hokkaido University, Sapporo, Japan) ,  Minato Shin-ichi (Kyoto University, Kyoto, Japan)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12049  ページ： 211-222  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 与えられたグラフGとHにより,決定図を用いてGにおけるHのトポロジー的最小埋め込みを暗黙的に列挙する方法を提案した。著者らは,著者らの方法の有用な応用を,禁止されたトポロジー的マイニングによって特徴付けられるサブグラフを列挙するために示した。すなわち,平面外,直列並列,およびサボテン部分グラフである。計算実験は,著者らの方法が,与えられたグラフにおけるすべての平面サブグラフを,ナイーブなバックトラッキングベースの方法よりも,最大5桁高速で見つけることができることを示した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 位相幾何学 ,  *位相 ,  意思決定 ,  バックトラッキング ,  マイナ ,  サボテン科 ,  *部分グラフ

著者キーワード (5件)： グラフアルゴリズム ,  数え上げ問題 ,  意思決定図 ,  フロンティアベースの探索 ,  トポロジー的マイナー

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： 位相 ,  マイナー ,  埋め込み ,  サブグラフ ,  応用