Fugu-MT 論文翻訳(概要): Domain Design for the Cops and Robbers Problem

論文の概要: Domain Design for the Cops and Robbers Problem

arxiv url: http://arxiv.org/abs/2607.18274v1
Date: Mon, 15 Jun 2026 16:22:17 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-27 00:46:13.100949
Title: Domain Design for the Cops and Robbers Problem
Title（参考訳）: Cops と Robbers 問題のためのドメイン設計
Abstract要約: Cops と Robbers はグラフ理論においてよく研究されている問題である。警官はグラフをぐるぐる回って、強盗を捕まえようとします。成功すれば、このグラフは$k$-copwin'と呼ばれる。
参考スコア（独自算出の注目度）: 6.284767263654555
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Cops and Robbers is a well-studied problem in graph theory. The setting consists of a robber and one or more cops placed on an undirected graph. Taking turns moving throughout the graph, the cops try to capture the robber. The property of interest is whether $k$ cops suffice to ensure at least one cop occupies the same vertex as the robber, after a finite number of turns, given any configuration of their initial placement; if successful, the graph is referred to as ``$k$-copwin''. In this work, we cast the problem of determining whether a graph is $k$-copwin as a non-deterministic planning problem and use state-of-the-art planners to compute this property. The cop movement is cast as non-deterministic movement (to capture all possible strategies), while the robber movement is deterministic in nature. We also extend the base model using several variations from the graph theory literature.
Abstract（参考訳）: Cops と Robbers はグラフ理論においてよく研究されている問題である。設定は強盗と、1つ以上の警官が無向グラフ上に置かれる。警官はグラフをぐるぐる回って、強盗を捕まえようとします。興味のある性質は、$k$ copsが少なくとも1人の警官が強盗と同じ頂点を占有することを保証するのに十分であるかどうかであり、最初の配置の任意の構成が与えられた場合、そのグラフは ``$k$-copwin'' と呼ばれる。本研究では、グラフが非決定論的計画問題として$k$-copwinであるかどうかを判定し、最先端のプランナーを用いてこの特性を計算する。警官運動は非決定論的運動(全ての可能な戦略を捉えるために)として、強盗運動は本質的に決定論的である。また、グラフ理論の文献からいくつかのバリエーションを用いてベースモデルを拡張する。

関連論文リスト

Predicting The Cop Number Using Machine Learning [6.865656740940774]
グラフのコピー番号$c(G)$は、強盗の捕獲を保証するのに必要な最小の警官数として定義される。本稿では,機械学習手法とグラフニューラルネットワークがグラフのコーパス数をその構造特性から正確に予測できるかどうかを考察する。
論文参考訳（メタデータ） (2026-02-18T16:52:46Z)
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文参考訳（メタデータ） (2024-09-09T18:23:07Z)
Catch Me if You Can: Effective Honeypot Placement in Dynamic AD Attack Graphs [4.795837146925278]
我々は,大規模なアクティブディレクトリ(AD)攻撃グラフ上で,攻撃者とディフェンダーとの間のスタックルバーグゲームについて検討する。我々は,ハニーポットを観察できない単純な攻撃者と,可能な有能な攻撃者という2つのタイプの攻撃者を考える。
論文参考訳（メタデータ） (2023-12-28T04:31:08Z)
Multi-armed Bandit Learning on a Graph [0.0]
そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
論文参考訳（メタデータ） (2022-09-20T02:31:42Z)
Model Inversion Attacks against Graph Neural Networks [65.35955643325038]
グラフニューラルネットワーク(GNN)に対するモデル反転攻撃について検討する。本稿では,プライベートトレーニンググラフデータを推測するためにGraphMIを提案する。実験の結果,このような防御効果は十分ではないことが示され,プライバシー攻撃に対するより高度な防御が求められている。
論文参考訳（メタデータ） (2022-09-16T09:13:43Z)
Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees [60.61846004535707]
グラフニューラルネットワーク(GNN)は多くのグラフベースのタスクで最先端のパフォーマンスを達成した。攻撃者はグラフ構造をわずかに摂動させることでGNNモデルを誤解させることができる。本稿では,構造摂動を伴うGNNに対するブラックボックス攻撃と理論的保証について考察する。
論文参考訳（メタデータ） (2022-05-07T04:17:25Z)
Source Free Unsupervised Graph Domain Adaptation [60.901775859601685]
Unsupervised Graph Domain Adaptation (UGDA) はノード分類のラベル付けコストを削減するための実用的価値を示している。既存のUGDAメソッドの多くは、ソースドメインのラベル付きグラフに大きく依存している。現実のシナリオでは、ソースグラフはプライバシーの問題のためにアクセスできない。我々は、Source Free Unsupervised Graph Domain Adaptation (SFUGDA) という新しいシナリオを提案する。
論文参考訳（メタデータ） (2021-12-02T03:18:18Z)
Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge [126.32842151537217]
現存する作品は通常、ホワイトボックス方式で攻撃を行う。ブラックボックス駆動で様々なグラフ埋め込みモデルに対処する必要がある。 GF-Attackはグラフ埋め込みモデルの層数を知ることなく効果的な攻撃を行うことができることを示す。
論文参考訳（メタデータ） (2021-05-26T09:18:58Z)
Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文参考訳（メタデータ） (2020-12-10T15:40:07Z)
Multi-officer Routing for Patrolling High Risk Areas Jointly Learned from Check-ins, Crime and Incident Response Data [6.295207672539996]
我々は、チェックイン、犯罪、インシデント対応データ、およびPOI情報を用いて、複数の警察官に対する動的犯罪パトロール計画問題を定式化する。本稿では,可能解の表現のための共同学習法と非ランダム最適化法を提案する。提案手法の性能検証と実世界のデータセットを用いたいくつかの最先端手法との比較を行った。
論文参考訳（メタデータ） (2020-07-31T23:33:14Z)
Graph Structure Learning for Robust Graph Neural Networks [63.04935468644495]
グラフニューラルネットワーク(GNN)は、グラフの表現学習において強力なツールである。近年の研究では、GNNは敵攻撃と呼ばれる、慎重に構築された摂動に弱いことが示されている。本稿では,構造グラフと頑健なグラフニューラルネットワークモデルを共同で学習できる汎用フレームワークであるPro-GNNを提案する。
論文参考訳（メタデータ） (2020-05-20T17:07:05Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。