[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/872746.873144guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

Universal Traversal Sequences with Backtracking

Published: 18 June 2001 Publication History

Abstract

Abstract: In this paper we introduce a new notion of traversal sequences that we call exploration sequences. Exploration sequences share many properties with the traversal sequences defined in [AKL+], but they also exhibit some new properties. In particular, they have an ability to backtrack, and their random properties are robust under choice of the probability distribution on labels. Further, we present extremely simple constructions of polynomial length universal exploration sequences for some previously studied classes of graphs (e.g., 2-regular graphs, cliques, expanders), and we also present universal exploration sequences for trees. Our constructions beat previously known lower-bounds on the length of universal traversal sequences.

Cited By

View all
  1. Universal Traversal Sequences with Backtracking

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image Guide Proceedings
    CCC '01: Proceedings of the 16th Annual Conference on Computational Complexity
    June 2001

    Publisher

    IEEE Computer Society

    United States

    Publication History

    Published: 18 June 2001

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2013)Delays Induce an Exponential Memory Gap for Rendezvous in TreesACM Transactions on Algorithms (TALG)10.1145/2438645.24386499:2(1-24)Online publication date: 1-Mar-2013
    • (2010)Delays induce an exponential memory gap for rendezvous in treesProceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures10.1145/1810479.1810524(224-232)Online publication date: 13-Jun-2010
    • (2008)Undirected connectivity in log-spaceJournal of the ACM (JACM)10.1145/1391289.139129155:4(1-24)Online publication date: 18-Sep-2008
    • (2007)Tree exploration with logarithmic memoryProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283446(585-594)Online publication date: 7-Jan-2007
    • (2006)The reduced automata technique for graph exploration space lower boundsTheoretical Computer Science10.5555/2168303.2168304(1-26)Online publication date: 1-Jan-2006
    • (2005)An O(log n log log n) space algorithm for undirected st-connectivityProceedings of the thirty-seventh annual ACM symposium on Theory of computing10.1145/1060590.1060684(626-633)Online publication date: 22-May-2005
    • (2005)Undirected ST-connectivity in log-spaceProceedings of the thirty-seventh annual ACM symposium on Theory of computing10.1145/1060590.1060647(376-385)Online publication date: 22-May-2005
    • (2003)Multiple-level grid algorithm for getting 2D road map in 3D virtual sceneProceedings of the 2003 international conference on Computational science: PartIII10.5555/1762418.1762447(264-274)Online publication date: 2-Jun-2003

    View Options

    View options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media