文献

J-GLOBAL ID：202102224015143927   整理番号：21A0444840

平面グラフ(およびそれ以上)のための隣接ラベリング【JST・京大機械翻訳】

Adjacency Labelling for Planar Graphs (and Beyond)

著者 (6件)： Dujmovic Vida (School of Computer Science and Electrical Engineering, University of Ottawa,Ottawa,Canada) ,  Esperet Louis (Laboratoire G-SCOP, CNRS, Univ. Grenoble Alpes,Grenoble,France) ,  Gavoille Cyril (LaBRI, University of Bordeaux,Bordeaux,France) ,  Joret Gwenael (Universite ́ Libre de Bruxelles,Departement d’Informatique,Brussels,Belgium) ,  Micek Piotr (Jagiellonian University,Faculty of Math. and Comp. Sci.,Theoretical Computer Science Department,Krako ́w,Poland) ,  Morin Pat (School of Computer Science, Carleton University,Ottawa,Canada)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2020  号： FOCS  ページ： 577-588  発行年： 2020年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： n頂点平面グラフGの各頂点が(1+o(1))log_2nビットラベルに割り当てられ,2頂点uとvのラベルが,uvがGのエッジであるかどうかを決定するために,平面グラフのための隣接ラベリング方式が存在することを示す。これは低次項まで最適であり,そのような漸近的最適結果である。この結果の代替法は,あらゆる正整数nに対して,n1+o(1)頂点を持つグラフU_nが存在し,n-頂点平面グラフがU_nの誘起部分グラフであるような,n1+o(1)頂点を持つグラフU_nが存在する。これらの結果は,有界属グラフ,頂点-マイナーグラフ,マイナーな閉じたファミリーからの有界度グラフ,およびk-平面グラフを含む,多くの他のグラフクラスに一般化する。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *平面グラフ ,  部分グラフ ,  マイナ
準シソーラス用語： 有界 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (2件)： 平面グラフ ,  ラベリング