MISC

2014年

Depth-First Search Using O(n) Bits

ALGORITHMS AND COMPUTATION, ISAAC 2014
  • Tetsuo Asano
  • ,
  • Taisuke Izumi
  • ,
  • Masashi Kiyomi
  • ,
  • Matsuo Konagaya
  • ,
  • Hirotaka Ono
  • ,
  • Yota Otachi
  • ,
  • Pascal Schweitzer
  • ,
  • Jun Tarui
  • ,
  • Ryuhei Uehara

8889
開始ページ
553
終了ページ
564
記述言語
英語
掲載種別
DOI
10.1007/978-3-319-13075-0_44
出版者・発行元
SPRINGER-VERLAG BERLIN

We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in polynomial time. Furthermore, we show that DFS on a directed acyclic graph can be done in space n/2(Omega(root log n)) and in polynomial time, and we also give a simple linear-time O(log n)-space algorithm for the depth-first traversal of an undirected tree. Finally, we also show that for a graph having an O(1)-size feedback set, DFS can be done in O(log n) space. Our algorithms are based on the analysis of properties of DFS and applications of the s-t connectivity algorithms due to Reingold and Barnes et al., both of which run in sublinear space.

Web of Science ® 被引用回数 : 11

リンク情報
DOI
https://doi.org/10.1007/978-3-319-13075-0_44
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000354865900044&DestApp=WOS_CPL
URL
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84921632467&origin=inward
ID情報
  • DOI : 10.1007/978-3-319-13075-0_44
  • ISSN : 0302-9743
  • SCOPUS ID : 84921632467
  • Web of Science ID : WOS:000354865900044

エクスポート
BibTeX RIS