文献

J-GLOBAL ID：202202291260293693   整理番号：22A0468187

ペブルアサインメントグラフの特性について

On Properties of Pebble Assignment Graphs

著者 (3件)： Lind M. (Princeton University, Princeton, NJ, USA) ,  Fiorini E. (DIMACS-Rutgers University, Piscataway, NJ, USA) ,  Woldar A. (Villanova University, Villanova, PA, USA)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 38  号： 2  ページ： 45  発行年： 2022年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 有限単純グラフG上のペブルアサインメント(S_G)は,Gの頂点上の有限個のペブルの分布である。標準的なペブルの動きは,Gの一つの頂点xから二つのペブルを取除く一方で,xに隣接する一つの頂点に一つのペブルを追加することで構成する。本論文では,ペブルアサインメントグラフに新しい概念を導入する。形式的には,これはハッセ図[S_G]であり,そのノードは一連のペブルの動きを適用することにより(S_G)から到達できる全てのアサインメントに対応している。[S_G]のエッジは,1回のペブルの動き(すなわち「親」から「子」へ)を介して他方から到達できる任意の二つのアサインメントに隣接する。グラフのこの新しいクラスの特性を調べ,どの抽象グラフがペブルアサインメントグラフとして実現できるか,さらにどのグラフGについて[S_G][数式:原文を参照]Gのようなアサインメント(S_G)が存在するかというような問題を扱う。Copyright The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2022 Translated from English into Japanese by JST.

シソーラス用語： *分配 ,  *グラフ理論 ,  頂点 ,  サイクル ,  端部 ,  *移動 ,  分類 ,  部分グラフ ,  範囲
準シソーラス用語： エッジ ,  クラス ,  二部グラフ ,  *割当 ,  近傍

著者キーワード (4件)： ペブリング ,  ペブル割当 ,  ペブル割当グラフ ,  完全横断可能割当

分類 (1件)： グラフ理論基礎  (IA02020S)