Skip to main content
Taylor & Francis Group Logo
    Advanced Search

    Click here to search products using title name,author name and keywords.

    • Login
    • Hi, User  
      • Your Account
      • Logout
      Advanced Search

      Click here to search products using title name,author name and keywords.

      Breadcrumbs Section. Click here to navigate to respective pages.

      Chapter

      Spanning Trees
      loading

      Chapter

      Spanning Trees

      DOI link for Spanning Trees

      Spanning Trees book

      Spanning Trees

      DOI link for Spanning Trees

      Spanning Trees book

      ByJonathan L. Gross, Jay Yellen, Mark Anderson
      BookGraph Theory and Its Applications

      Click here to navigate to parent product.

      Edition 3rd Edition
      First Published 2018
      Imprint Chapman and Hall/CRC
      Pages 55
      eBook ISBN 9780429425134
      Share
      Share

      ABSTRACT

      This chapter demonstrates that several classical algorithms, including depth-first and breadth-first searches, Prim's minimum-spanning-tree method, and Dijkstra's shortest-path method, are special cases or extensions of spanning tree strategy. Spanning trees also provide a foundation for a systematic analysis of the cycle structure of a graph. Depth-first search and breadth-first search are integral parts of numerous algorithms used in computer science, operations research, and other engineering disciplines. Tree-growing for digraphs looks the same as for undirected graphs: in each iteration, a frontier arc is selected and added to the growing tree. The forest-growing scheme is simply the repeated application of Tree-Growing. The Steiner-tree problem often arises in network-design and wiring-layout problems. The chapter establishes a number of properties that highlight the relationship and a certain duality between the edge-cuts and cycles of a graph. One approach trying to solve the maximum-weight problem associated with a hereditary subset system is the simple algorithm known as the greedy algorithm.

      T&F logoTaylor & Francis Group logo
      • Policies
        • Privacy Policy
        • Terms & Conditions
        • Cookie Policy
        • Privacy Policy
        • Terms & Conditions
        • Cookie Policy
      • Journals
        • Taylor & Francis Online
        • CogentOA
        • Taylor & Francis Online
        • CogentOA
      • Corporate
        • Taylor & Francis Group
        • Taylor & Francis Group
        • Taylor & Francis Group
        • Taylor & Francis Group
      • Help & Contact
        • Students/Researchers
        • Librarians/Institutions
        • Students/Researchers
        • Librarians/Institutions
      • Connect with us

      Connect with us

      Registered in England & Wales No. 3099067
      5 Howick Place | London | SW1P 1WG © 2022 Informa UK Limited