回避可能な経路へのシフト経路【JST・京大機械翻訳】

Gurvich Vladimir; Krnc Matjaz; Milanic Martin; Milanic Martin; Vyalyi Mikhail; Vyalyi Mikhail; Vyalyi Mikhail

文献

J-GLOBAL ID：202202264433081935 整理番号：22A0950601

回避可能な経路へのシフト経路【JST・京大機械翻訳】

Shifting paths to avoidable ones

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=22A0950601&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=22A0950601&from=J-GLOBAL&jstjournalNo=C0773B") }}

著者 (7件)： , , , , , ,
資料名：
巻： 100 号： 1 ページ： 69-83 発行年： 2022年
JST資料番号： C0773B ISSN： 0364-9024 CODEN： JGTHD 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

グラフ[数式:原文を参照]における誘導経路[数式:原文を参照]の拡張は,[数式:原文を参照]のエンドポイントを削除するような誘導経路[数式:原文を参照]である。グラフにおける誘導経路は,その拡張の各々が誘導サイクルに含まれるならば避けられないと言われている。2019,Beisegel,Chudovsky,Gurvich,MilanicおよびServatiusは,誘導[数式:原文を参照]-頂点経路を含むあらゆるグラフが,同じ長さの回避可能な誘導経路を含み,[数式:原文を参照]の結果を証明した。1976年には,Ohtsuki,Cheung,およびFujisawaの仕事により,[数式:原文を参照]がはるかに早く知られていた。予想は,Bonamy,Defrain,Hatzel,およびThiebautによって2020年にすべての[数式:原文を参照]に対して証明された。本論文では,同様の手法を用いて,再構成の観点からそれらの結果を強化する。すなわち,各グラフにおいて,各誘導経路はシフトのシーケンスにより回避可能なものに変換できることを示し,そこでは,2つの誘導[数式:原文を参照]-頂点経路は,それらの結合が[数式:原文を参照]頂点を持つ誘導経路であるならば互いにシフトする。また,必ずしも誘導されない経路と歩行に対して類似の結果を得る。対照的に,ステートメントは,トレイルまたは等尺性経路に拡張できない。Copyright 2022 Wiley Publishing Japan K.K. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

, , , , , ,
, 【Automatic Indexing@JST】

著者キーワード (10件)： , , , , , , , , ,

グラフ理論基礎

, ,

前のページに戻る