Abstract/Details

A DEPTH-FIRST SEARCH CHARACTERIZATION OF K-CONNECTIVITY AND ITS APPLICATION TO CONNECTIVITY TESTING


1981 1981

Other formats: Order a copy

Abstract (summary)

The vertex connectivity of an undirected graph is explored with regard to a depth-first search analysis. This analysis leads to a separating set characterization theorem of a very general nature. The strength of this characterization is illustrated by an application to triconnectivity testing. The resulting preorder algorithm will list all non-degenerate separating pairs in time O(E(alpha)(E,V)+(mu)(,2)) and space O(E) where (mu)(,2) is the number of separating pairs. This characterization also suggests an O(ElogE) algorithm for 4-connectivity testing. Some preliminary results for this algorithm are presented.

Indexing (details)


Subject
Computer science
Classification
0984: Computer science
Identifier / keyword
Applied sciences
Title
A DEPTH-FIRST SEARCH CHARACTERIZATION OF K-CONNECTIVITY AND ITS APPLICATION TO CONNECTIVITY TESTING
Author
MYERS, EUGENE WIMBERLY, JR.
Number of pages
144
Publication year
1981
Degree date
1981
School code
0051
Source
DAI-B 42/04, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
University/institution
University of Colorado at Boulder
University location
United States -- Colorado
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
8122309
ProQuest document ID
303089828
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/303089828/
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.