暗黙のグラフ

グラフアルゴリズムの研究において、暗黙的なグラフ表現(または単に暗黙的なグラフ) とは、頂点や辺がコンピュータのメモリ内で明示的なオブジェクトとして表現されるのではなく、計算可能な関数などの他の入力からアルゴリズム的に決定されるグラフです。

近隣地域の表現

暗黙のグラフの概念は、グラフの観点で説明されるさまざまな検索アルゴリズムで一般的です。この文脈では、暗黙のグラフは、指定された任意の頂点のすべての近傍を定義する一連のルールとして定義できます。^[1]このタイプの暗黙のグラフ表現は、各頂点の近傍に簡単にアクセスできるという点で、隣接リストに似ています。たとえば、ルービックキューブなどのパズルの解を探す場合、各頂点がキューブの可能な状態の1つを表し、各辺が1つの状態から別の状態への動きを表す暗黙のグラフを定義できます。パズルのすべての可能な動きを試し、これらの動きのそれぞれによって到達した状態を決定することで、任意の頂点の近傍を生成するのは簡単です。ただし、ルービックキューブの状態空間は大きすぎて、アルゴリズムですべての状態をリストすることはできないため、暗黙の表現が必要です。^[2]

計算複雑性理論では、上記のように頂点の近傍をリストするための規則またはアルゴリズムによって定義される暗黙的グラフに関連して、いくつかの計算複雑性クラスが定義されています。たとえば、 PPAは、入力として無向暗黙的グラフ (頂点は $n$ ビットのバイナリ文字列で、任意の頂点の近傍をリストするための多項式時間アルゴリズムを持つ) とグラフ内の奇数次数の頂点が与えられ、奇数次数の 2 番目の頂点を見つけなければならない問題のクラスです。ハンドシェイク補題により、そのような頂点は存在します。1 つを見つけることはNPの問題ですが、この方法で定義できる問題は、PPA = NP であるかどうかが不明であるため、必ずしもNP 完全であるとは限りません。PPAD は、暗黙的有向グラフ上で定義される類似のクラスであり、ナッシュ均衡を計算する問題を含むため、アルゴリズムゲーム理論で注目を集めています。^[3]暗黙的グラフ内のある頂点から別の頂点への到達可能性をテストする問題は、 NL （頂点が $O(log$ $n$ $)$ ビットのビット文字列である暗黙的有向グラフの到達可能性によって特徴付けられる問題のクラス）、SL（無向グラフの類似クラス）、PSPACE（多項式長のビット文字列を持つ暗黙的グラフの到達可能性によって特徴付けられる問題のクラス）を含む、空間制限のある非決定性複雑性クラスを特徴付けるためにも使用できます。この複雑性理論のコンテキストでは、暗黙的グラフの頂点は非決定性チューリングマシンの状態を表し、エッジは可能な状態遷移を表しますが、暗黙的グラフは他の多くのタイプの組み合わせ構造を表すためにも使用できます。^{[4]別の複雑性クラスである}PLS は、暗黙的グラフで局所最適値を見つける複雑さを捉えます。^[5]

暗黙的グラフモデルは、相対化されていないモデルの既知の分離よりも強い複雑性クラス間の分離を証明するための相対化の一形態としても使用されてきました。たとえば、Childsらは暗黙的グラフの近傍表現を使用して、量子コンピュータでは多項式時間で解決できるが、古典的なコンピュータでは指数時間で解決する必要があるグラフトラバーサル問題を定義しました。^[6]

隣接ラベル付けスキーム

グラフの効率的な表現の文脈において、JH Muller は、与えられたグラフのファミリー $F$ 内のグラフ $Gの$ ローカル構造または隣接ラベル付けスキームを、 $G$ の各頂点に $O$ $(log$ $n$ $)$ ビットの識別子を割り当てることと、2 つの頂点識別子を入力として受け取り、それらが G 内の辺の端点であるかどうかを判断するアルゴリズム ( $F$ に依存する可能性があるが、個々のグラフ $Gからは独立している$ $)$ であると定義しました。つまり、このタイプの暗黙的な表現は隣接行列に似ています。2 つの頂点が隣接しているかどうかを確認するのは簡単ですが、任意の頂点の隣接頂点を見つけるには、すべての頂点をループして、どの頂点が隣接しているかをテストする必要がある場合があります。^[7]

隣接ラベル付けスキームを持つグラフファミリには次のものがあります。

有界次数グラフ: $G$ の各頂点が最大 $d個の隣接頂点を持つ場合、$ $G$ の頂点に1 から $n$ までの番号を付け、頂点の識別子をその頂点の番号と隣接頂点の番号の $(d + 1)$ 組とします。2 つの頂点は、一方の識別子の最初の番号がもう一方の識別子の後に現れるときに隣接しています。より一般的には、同じアプローチを使用して、平面グラフや任意のマイナー閉グラフ族のグラフを含む、有界樹状性または有界退化を持つグラフの暗黙的な表現を提供できます。^[8]^[9]
交差グラフ: 区間グラフは、実数直線上の線分の集合の交差グラフである。このグラフには、線分の端点となる点に 1 から 2 nまでの番号が付けられ、グラフの各頂点は対応する区間の 2 つの端点の番号で表す隣接ラベル付けスキームが与えられる場合がある。この表現では、2 つの頂点を表す番号を比較し、これらの番号が重複区間を定義していることを確認することで、2 つの頂点が隣接しているかどうかをチェックできる。同じアプローチは、境界付き箱型グラフや円グラフ、および距離遺伝グラフやコグラフなどのこれらのファミリーのサブファミリーを含む他の幾何学的交差グラフにも適用できる。 [ 8 ] [ 10 ^]^ただし、幾何学的交差グラフの表現は、各幾何学的オブジェクトを指定するために対数以上のビット数が必要になる場合があるため、隣接ラベル付けスキームの存在を常に意味するわけではない。たとえば、グラフを単位円グラフとして表すと、円の中心の座標に指数的に多くのビットが必要になる場合がある。^[11]
低次元比較グラフ: 半順序集合の比較可能性グラフには、各集合要素の頂点と、半順序によって関連付けられた 2 つの集合要素間の辺があります。半順序の順序次元は、与えられた半順序が交差する線形順序の最小数です。半順序が制限された順序次元を持つ場合、その比較可能性グラフの頂点の隣接ラベル付けスキームは、各定義線形順序での位置で各頂点にラベルを付け、ラベル内の対応する数字の各ペアが他のペアと同じ順序関係にある場合に 2 つの頂点が隣接していると判断することによって定義できます。特に、これにより、最大 4 次元の半順序から得られる弦比較可能性グラフの隣接ラベル付けスキームが可能になります。 ^[12]^[13]

暗黙のグラフ予想

数学における未解決の問題:

ゆっくり成長する遺伝的グラフ族には必ず暗黙的な表現があるのでしょうか?

（数学における未解決の問題がさらに増える）

すべてのグラフ族が局所構造を持っているわけではない。いくつかの族については、単純な計数議論によって隣接ラベリング方式が存在しないことが証明される。グラフ全体を表すのに $O (n log n)$ ビットしか使用できないため、このタイプの表現は、与えられた族 $F内の$ $n頂点グラフの数が最大で$ $2$ $O$ $($ $n$ $log$ $n$ $)$ である場合にのみ存在できる。二部グラフや三角形のないグラフなど、これよりも多くのグラフを持つグラフ族には、隣接ラベリング方式がない。^[8]^[10]ただし、族内のグラフの数が少ないグラフ族でも、隣接ラベリング方式がない可能性がある。たとえば、頂点よりも辺の数が少ないグラフ族には $2$ $O$ $($ $n$ $log$ $n$ $)$ $n$ 頂点グラフがあるが、隣接ラベリング方式がない。これは、この族では、ラベル付け可能性を変更せずに、各辺に新しい孤立した頂点を追加することで、任意のグラフをより大きなグラフに変換できるためである。^[7]^[10] Kannanらは、禁制部分グラフの特徴付けと最大 $2$ $O$ $($ $nlogn$ $)$ $n頂点グラフを持つことが$ $、$ 隣接ラベル付けスキームの存在を保証するのに十分かどうかを尋ねた。Spinradが予想として言い換えたこの質問は未解決のままである。 $[$ ^8]^[10] この予想の条件を満たし、隣接ラベル付けスキームが知られていないグラフ族の中には、ディスクグラフと線分交差グラフの族がある。

ラベリングスキームと誘導ユニバーサルグラフ

グラフ族 $F$ が隣接ラベリング方式を持つ場合、 $F内の$ $n$ 頂点グラフは、すべての可能な頂点識別子からなる多項式サイズの共通誘導ユニバーサルグラフの誘導サブグラフとして表現できます。逆に、このタイプの誘導ユニバーサルグラフが構築できる場合は、その頂点のアイデンティティを隣接ラベリング方式のラベルとして使用できます。 ^[8]この暗黙のグラフ表現のアプリケーションでは、ラベルのビット数が誘導ユニバーサルグラフの頂点数に直接変換されるため、ラベルができる限り少ないビットを使用することが重要です。 Alstrup と Rauhe は、任意のツリーがラベルあたり $log$ $2$ $n$ $+$ $O$ $($ $log$ $*$ $n$ $)$ ビットの隣接ラベリング方式を持つことを示しました。このことから、樹木度kを持つ任意のグラフは、ラベルあたり $k$ $log$ $2$ $n$ $+$ $O$ $($ $log$ $*$ $n$ $)ビットの方式と$ $n$ $k$ $2$ $O$ $($ $log$ $*$ $n$ $)$ 頂点を持つユニバーサルグラフを持つことになります。特に、平面グラフは樹状性が最大で 3 であるため、頂点数がほぼ 3 のユニバーサルグラフになります。^{[14]この境界は Gavoille と Labourel によって改良され、平面グラフとマイナー閉グラフファミリはラベルあたり} $2 log$ $2$ $n$ $+$ $O$ $(log log$ $n$ $)$ ビットのラベル付けスキームを持ち、木幅が制限されたグラフはラベルあたり $log$ $2$ $n$ $+$ $O$ $(log log$ $n$ $)$ ビットのラベル付けスキームを持つことが示されました。 ^[15] 平面グラフの境界は、Bonamy、Gavoille、および Piliczuk によってさらに改良され、平面グラフはラベルあたり $(4/3+o(1))log$ $2$ $n$ ビットのラベル付けスキームを持つことが示されました。^[16] 最後に、Dujmović らは、平面グラフはラベルあたり $(1+o(1))log$ $2$ $nビットのラベル付けスキームを持ち、$ $n$ $1+o(1)$ 頂点のユニバーサルグラフになることを示しました。^[17]

回避性

Aanderaa -Karp-Rosenberg 予想は、任意の 2 つの頂点が隣接しているかどうかを判断するためのブラックボックスルールを持つ、ラベル付けされた頂点の集合として与えられた暗黙のグラフに関するものです。この定義は、ルールがファミリ内のすべてのグラフに適用される一般的なルールではなく、特定のグラフに固有のものである可能性があるという点で、隣接ラベル付けスキームとは異なります。この違いにより、すべてのグラフには暗黙の表現があります。たとえば、ルールは別の隣接行列で頂点のペアを検索するというものです。ただし、このタイプの暗黙のグラフが入力として与えられたアルゴリズムは、テストの実装方法に関係なく、暗黙の隣接テストのみを介してグラフを操作しなければなりません。

グラフ特性とは、グラフが与えられたグラフ族に属するかどうかという問題であり、その答えは頂点のラベル付けを変更しても不変でなければならない。この文脈で決定すべき問題は、与えられた暗黙のグラフについて、関心のある特性が真か偽かを判定する前に、最悪の場合、何組の頂点の隣接性を検査しなければならないかである。Rivest と Vuillemin は、任意の非自明なグラフ特性に対する決定論的アルゴリズムは、頂点の二乗個のペアを検査しなければならないことを証明した。^[18]完全な Aanderaa–Karp–Rosenberg 予想は、単調なグラフ特性 (その特性を持つグラフにさらに辺を追加しても真のままであるもの) に対する決定論的アルゴリズムは、場合によってはすべての可能な頂点のペアを検査しなければならないというものである。この予想のいくつかのケースは正しいことが証明されています。例えば、頂点の数が素数であるグラフでは正しいことが知られています^[19]が、完全な予想は未解決のままです。ランダム化アルゴリズムと量子アルゴリズムの問題の変種も研究されています。

ベンダーとロンは、回避性予想に使用されたのと同じモデルで、有向非巡回グラフと非巡回からほど遠いグラフを区別するのに定数時間しかかからないことを示した。対照的に、近傍ベースの暗黙的グラフモデルでは、そのような高速な時間は不可能である。^[20]

参照

ブラックボックス群、群論的アルゴリズムの暗黙的モデル
マトロイドオラクル、マトロイドアルゴリズムの暗黙モデル

参考文献

^ Korf, Richard E. (2008)、「線形時間ディスクベースの暗黙的グラフ検索」、Journal of the ACM、55 (6)、Article 26、40pp、doi :10.1145/1455248.1455250、MR 2477486、S2CID 13969607。
^ Korf, Richard E. (2008)、「2 ビット幅優先探索におけるディスク I/O の最小化」(PDF)、Proc. 23rd AAAI Conf. on Artificial Intelligence、pp. 317–324、標準の 3×3×3 ルービックキューブには 4.3252 × 10 ^{19 の}状態が含まれており、網羅的に探索するには大きすぎます。
^ Papadimitriou, Christos (1994)、「パリティ議論の複雑さと存在のその他の非効率的な証明について」(PDF)、Journal of Computer and System Sciences、48 (3): 498–532、doi :10.1016/S0022-0000(05)80063-7、2016-03-04にオリジナル(PDF)からアーカイブ、2011-07-12に取得
^ Immerman, Neil (1999)、「演習 3.7 (すべてがグラフ)」、記述的複雑性、コンピュータサイエンスの大学院テキスト、Springer-Verlag、p. 48、ISBN 978-0-387-98600-5。
^ Yannakakis, Mihalis (2009)、「均衡、不動点、複雑性クラス」、Computer Science Review、3 (2): 71–85、arXiv : 0802.2831、doi :10.1016/j.cosrev.2009.03.004。
^ Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003)、「量子ウォークによる指数的アルゴリズムの高速化」、第35回ACMコンピューティング理論シンポジウムの議事録、ニューヨーク：ACM、pp. 59–68、arXiv：quant-ph/0209131、doi：10.1145/780542.780552、ISBN 1-58113-674-9、MR 2121062、S2CID 308884。
^ ab Muller, John Harold (1988)、グラフクラスの局所構造、ジョージア工科大学博士論文。
^ abcde Kannan, Sampath; Naor, Moni ; Rudich, Steven (1992)、「グラフの暗黙的表現」、SIAM Journal on Discrete Mathematics、5 (4): 596–603、doi :10.1137/0405049、MR 1186827。
^ Chrobak, Marek; Eppstein, David (1991)、「低い出次数を持つ平面配向と隣接行列の圧縮」(PDF)、理論計算機科学、86 (2): 243–266、doi : 10.1016/0304-3975(91)90020-3。
^ abcd Spinrad, Jeremy P. (2003)、「2. 暗黙のグラフ表現」、効率的なグラフ表現、アメリカ数学会、pp. 17–30、ISBN 0-8218-2815-0。
^ Kang, Ross J.; Müller, Tobias (2011)、グラフの球面およびドット積表現(PDF) 、 2012-03-16 にオリジナル(PDF)からアーカイブ、 2011-07-12取得。
^ Ma, Tze Heng; Spinrad, Jeremy P. (1991)、「サイクルフリー部分順序と弦比較グラフ」、Order、8 (1): 49–61、doi :10.1007/BF00385814、MR 1129614、S2CID 120479154。
^ Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010)、「線形時間における弦比較グラフの暗黙的表現」、Discrete Applied Mathematics、158 (8): 869–875、doi : 10.1016/j.dam.2010.01.005、MR 2602811。
^ Alstrup, Stephen; Rauhe, Theis (2002)、「小さな誘導ユニバーサルグラフとコンパクトな暗黙のグラフ表現」(PDF)、第43回IEEEコンピュータサイエンス基礎シンポジウム議事録、pp. 53–62、doi :10.1109/SFCS.2002.1181882、ISBN 0-7695-1822-2、S2CID 1820524、 2011年9月27日にオリジナル（PDF）からアーカイブ、2011年7月13日に取得。
^ Arnaud, Labourel; Gavoille, Cyril (2007)、「平面グラフと木幅制限付きグラフのより短い暗黙的表現」(PDF)、第 15 回ヨーロッパアルゴリズムシンポジウムの議事録、コンピュータサイエンスの講義ノート、第 4698 巻、pp. 582–593、doi :10.1007/978-3-540-75520-3_52、ISBN 978-3-540-75519-7。
^ ボナミー、マルテ、ガヴォイル、シリル、ピリプチュク、ミハウ (2020)、「平面グラフの短縮ラベル付けスキーム」、2020 ACM-SIAM 離散アルゴリズムシンポジウムの議事録、pp. 446–462、arXiv : 1908.03341、doi :10.1007/978-3-540-75520-3_52。
^ ドゥイモヴィッチ、ヴィダ;ルイス、エスペレット。ジョレット、グエナエル。ガヴォイユ、シリル。ミチェク、ピョートル。パット・モーリン (2020)、「平面グラフの隣接ラベル付け (およびその先)」、第 61 回 IEEE 年次シンポジウム・オン・ファウンデーション・オブ・コンピューター・サイエンス、pp. 577–588、arXiv : 2003.04280、doi :10.1007/978-3-540-75520 -3_52。
^ Rivest, Ronald L. ; Vuillemin, Jean (1975)、「A generalization and proof of the Aanderaa-Rosenberg conjecture」、Proc. 7th ACM Symposium on Theory of Computing、アルバカーキ、ニューメキシコ州、アメリカ合衆国、pp. 6–11、CiteSeerX 10.1.1.309.7236、doi :10.1145/800116.803747、S2CID 16220596 {{citation}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)。
^ カーン、ジェフ、サックス、マイケル、スターテバント、ディーン (1983)、「回避性へのトポロジカルアプローチ」、コンピュータサイエンスの基礎に関するシンポジウム、ロサンゼルス、カリフォルニア州、米国: IEEE コンピュータ協会、pp. 31–33、doi :10.1109/SFCS.1983.4、ISBN 0-8186-0508-1。
^ Bender, Michael A.; Ron, Dana (2000)、「有向グラフの非巡回性をサブリニア時間でテストする」、Automata, languages and programming (ジュネーブ、2000)、Lecture Notes in Comput. Sci.、vol. 1853、ベルリン: Springer、pp. 809–820、doi :10.1007/3-540-45022-X_68、ISBN 978-3-540-67715-4、MR 1795937。

[1] Korf, Richard E. (2008)、「線形時間ディスクベースの暗黙的グラフ検索」、Journal of the ACM、55 (6)、Article 26、40pp、doi :10.1145/1455248.1455250、MR 2477486、S2CID 13969607。

[2] Korf, Richard E. (2008)、「2 ビット幅優先探索におけるディスク I/O の最小化」(PDF)、Proc. 23rd AAAI Conf. on Artificial Intelligence、pp. 317–324、標準の 3×3×3 ルービックキューブには 4.3252 × 10 ^{19 の}状態が含まれており、網羅的に探索するには大きすぎます。

[3] Papadimitriou, Christos (1994)、「パリティ議論の複雑さと存在のその他の非効率的な証明について」(PDF)、Journal of Computer and System Sciences、48 (3): 498–532、doi :10.1016/S0022-0000(05)80063-7、2016-03-04にオリジナル(PDF)からアーカイブ、2011-07-12に取得

[4] Immerman, Neil (1999)、「演習 3.7 (すべてがグラフ)」、記述的複雑性、コンピュータサイエンスの大学院テキスト、Springer-Verlag、p. 48、ISBN 978-0-387-98600-5。

[5] Yannakakis, Mihalis (2009)、「均衡、不動点、複雑性クラス」、Computer Science Review、3 (2): 71–85、arXiv : 0802.2831、doi :10.1016/j.cosrev.2009.03.004。

[6] Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003)、「量子ウォークによる指数的アルゴリズムの高速化」、第35回ACMコンピューティング理論シンポジウムの議事録、ニューヨーク：ACM、pp. 59–68、arXiv：quant-ph/0209131、doi：10.1145/780542.780552、ISBN 1-58113-674-9、MR 2121062、S2CID 308884。

[muller-7] Muller, John Harold (1988)、グラフクラスの局所構造、ジョージア工科大学博士論文。

[knr-8] Kannan, Sampath; Naor, Moni ; Rudich, Steven (1992)、「グラフの暗黙的表現」、SIAM Journal on Discrete Mathematics、5 (4): 596–603、doi :10.1137/0405049、MR 1186827。

[9] Chrobak, Marek; Eppstein, David (1991)、「低い出次数を持つ平面配向と隣接行列の圧縮」(PDF)、理論計算機科学、86 (2): 243–266、doi : 10.1016/0304-3975(91)90020-3。

[spinrad-10] Spinrad, Jeremy P. (2003)、「2. 暗黙のグラフ表現」、効率的なグラフ表現、アメリカ数学会、pp. 17–30、ISBN 0-8218-2815-0。

[11] Kang, Ross J.; Müller, Tobias (2011)、グラフの球面およびドット積表現(PDF) 、 2012-03-16 にオリジナル(PDF)からアーカイブ、 2011-07-12取得。

[12] Ma, Tze Heng; Spinrad, Jeremy P. (1991)、「サイクルフリー部分順序と弦比較グラフ」、Order、8 (1): 49–61、doi :10.1007/BF00385814、MR 1129614、S2CID 120479154。

[13] Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010)、「線形時間における弦比較グラフの暗黙的表現」、Discrete Applied Mathematics、158 (8): 869–875、doi : 10.1016/j.dam.2010.01.005、MR 2602811。

[14] Alstrup, Stephen; Rauhe, Theis (2002)、「小さな誘導ユニバーサルグラフとコンパクトな暗黙のグラフ表現」(PDF)、第43回IEEEコンピュータサイエンス基礎シンポジウム議事録、pp. 53–62、doi :10.1109/SFCS.2002.1181882、ISBN 0-7695-1822-2、S2CID 1820524、 2011年9月27日にオリジナル（PDF）からアーカイブ、2011年7月13日に取得。

[15] Arnaud, Labourel; Gavoille, Cyril (2007)、「平面グラフと木幅制限付きグラフのより短い暗黙的表現」(PDF)、第 15 回ヨーロッパアルゴリズムシンポジウムの議事録、コンピュータサイエンスの講義ノート、第 4698 巻、pp. 582–593、doi :10.1007/978-3-540-75520-3_52、ISBN 978-3-540-75519-7。

[16] ボナミー、マルテ、ガヴォイル、シリル、ピリプチュク、ミハウ (2020)、「平面グラフの短縮ラベル付けスキーム」、2020 ACM-SIAM 離散アルゴリズムシンポジウムの議事録、pp. 446–462、arXiv : 1908.03341、doi :10.1007/978-3-540-75520-3_52。

[17] ドゥイモヴィッチ、ヴィダ;ルイス、エスペレット。ジョレット、グエナエル。ガヴォイユ、シリル。ミチェク、ピョートル。パット・モーリン (2020)、「平面グラフの隣接ラベル付け (およびその先)」、第 61 回 IEEE 年次シンポジウム・オン・ファウンデーション・オブ・コンピューター・サイエンス、pp. 577–588、arXiv : 2003.04280、doi :10.1007/978-3-540-75520 -3_52。

[18] Rivest, Ronald L. ; Vuillemin, Jean (1975)、「A generalization and proof of the Aanderaa-Rosenberg conjecture」、Proc. 7th ACM Symposium on Theory of Computing、アルバカーキ、ニューメキシコ州、アメリカ合衆国、pp. 6–11、CiteSeerX 10.1.1.309.7236、doi :10.1145/800116.803747、S2CID 16220596 {{citation}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)。

[19] カーン、ジェフ、サックス、マイケル、スターテバント、ディーン (1983)、「回避性へのトポロジカルアプローチ」、コンピュータサイエンスの基礎に関するシンポジウム、ロサンゼルス、カリフォルニア州、米国: IEEE コンピュータ協会、pp. 31–33、doi :10.1109/SFCS.1983.4、ISBN 0-8186-0508-1。

[20] Bender, Michael A.; Ron, Dana (2000)、「有向グラフの非巡回性をサブリニア時間でテストする」、Automata, languages and programming (ジュネーブ、2000)、Lecture Notes in Comput. Sci.、vol. 1853、ベルリン: Springer、pp. 809–820、doi :10.1007/3-540-45022-X_68、ISBN 978-3-540-67715-4、MR 1795937。