The Resource Efficient algorithms for listing combinatorial structures, Leslie Ann Goldberg

Efficient algorithms for listing combinatorial structures, Leslie Ann Goldberg

Label
Efficient algorithms for listing combinatorial structures
Title
Efficient algorithms for listing combinatorial structures
Statement of responsibility
Leslie Ann Goldberg
Creator
Author
Subject
Language
eng
Summary
First published in 1993, this thesis is concerned with the design of efficient algorithms for listing combinatorial structures. The research described here gives some answers to the following questions: which families of combinatorial structures have fast computer algorithms for listing their members? What general methods are useful for listing combinatorial structures? How can these be applied to those families which are of interest to theoretical computer scientists and combinatorialists? Amongst those families considered are unlabelled graphs, first order one properties, Hamiltonian graphs, graphs with cliques of specified order, and k-colourable graphs. Some related work is also included, which compares the listing problem with the difficulty of solving the existence problem, the construction problem, the random sampling problem, and the counting problem. In particular, the difficulty of evaluating Pólya's cycle polynomial is demonstrated
Member of
Cataloging source
UkCbUP
http://library.link/vocab/creatorName
Goldberg, Leslie Ann
Dewey number
511/.6
Index
index present
LC call number
QA76.9.A43
LC item number
G65 1993
Literary form
non fiction
Nature of contents
dictionaries
Series statement
Distinguished dissertations in computer science
http://library.link/vocab/subjectName
Computer algorithms
Label
Efficient algorithms for listing combinatorial structures, Leslie Ann Goldberg
Link
https://doi.org/10.1017/CBO9780511569913
Instantiates
Publication
Note
Title from publisher's bibliographic system (viewed on 05 Oct 2015)
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
1. Introduction. 1.1. Families of Combinatorial Structures. 1.2. Motivation. 1.3. Listing Algorithms. 1.4. Efficient Listing Algorithms. 1.5. Synopsis of the Thesis. 1.6. Bibliographic Notes -- 2. Techniques for Listing Combinatorial Structures. 2.1. Basic Building Blocks. 2.2. Using Listing Algorithms for Closely Related Families. 2.3. Avoiding Duplicates -- 3. Applications to Particular Families of Structures. 3.1. First Order Graph Properties. 3.2. Hamiltonian Graphs. 3.3. Graphs with Cliques of Specified Sizes. 3.4. Graphs which can be Colored with a Specified Number of Colors -- 4. Directions for Future Work on Listing -- 5. Related Results. 5.1. Comparing Listing with other Computational Problems. 5.2. Evaluating the Cycle Index Polynomial. 6. Bibliography
Extent
1 online resource (xv, 160 pages)
Form of item
online
Isbn
9780511569913
Isbn Type
(ebook)
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other physical details
digital, PDF file(s).
Specific material designation
remote
System control number
(UkCbUP)CR9780511569913
Label
Efficient algorithms for listing combinatorial structures, Leslie Ann Goldberg
Link
https://doi.org/10.1017/CBO9780511569913
Publication
Note
Title from publisher's bibliographic system (viewed on 05 Oct 2015)
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
1. Introduction. 1.1. Families of Combinatorial Structures. 1.2. Motivation. 1.3. Listing Algorithms. 1.4. Efficient Listing Algorithms. 1.5. Synopsis of the Thesis. 1.6. Bibliographic Notes -- 2. Techniques for Listing Combinatorial Structures. 2.1. Basic Building Blocks. 2.2. Using Listing Algorithms for Closely Related Families. 2.3. Avoiding Duplicates -- 3. Applications to Particular Families of Structures. 3.1. First Order Graph Properties. 3.2. Hamiltonian Graphs. 3.3. Graphs with Cliques of Specified Sizes. 3.4. Graphs which can be Colored with a Specified Number of Colors -- 4. Directions for Future Work on Listing -- 5. Related Results. 5.1. Comparing Listing with other Computational Problems. 5.2. Evaluating the Cycle Index Polynomial. 6. Bibliography
Extent
1 online resource (xv, 160 pages)
Form of item
online
Isbn
9780511569913
Isbn Type
(ebook)
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other physical details
digital, PDF file(s).
Specific material designation
remote
System control number
(UkCbUP)CR9780511569913

Library Locations

  • Architecture LibraryBorrow it
    Gould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US
    35.205706 -97.445050
  • Bizzell Memorial LibraryBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Boorstin CollectionBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Chinese Literature Translation ArchiveBorrow it
    401 W. Brooks St., RM 414, Norman, OK, 73019, US
    35.207487 -97.447906
  • Engineering LibraryBorrow it
    Felgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US
    35.205706 -97.445050
  • Fine Arts LibraryBorrow it
    Catlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US
    35.210371 -97.448244
  • Harry W. Bass Business History CollectionBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • History of Science CollectionsBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • John and Mary Nichols Rare Books and Special CollectionsBorrow it
    401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • Library Service CenterBorrow it
    2601 Technology Place, Norman, OK, 73019, US
    35.185561 -97.398361
  • Price College Digital LibraryBorrow it
    Adams Hall 102 307 West Brooks St., Norman, OK, 73019, US
    35.210371 -97.448244
  • Western History CollectionsBorrow it
    Monnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US
    35.209584 -97.445414
Processing Feedback ...