Borrow it
Coverart for item
The Resource Genetic theory for cubic graphs, Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe

Genetic theory for cubic graphs, Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe

Creator
Author
Contributor
Summary
This book was motivated by the notion that some of the underlying difficulty in challenging instances of graph-based problems (e.g., the Traveling Salesman Problem) may be "inherited" from simpler graphs which "in an appropriate sense" could be seen as "ancestors" of the given graph instance. The authors propose a partitioning of the set of unlabeled, connected cubic graphs into two disjoint subsets named genes and descendants, where the cardinality of the descendants dominates that of the genes. The key distinction between the two subsets is the presence of special edge cut sets, called cubic crackers, in the descendants. The book begins by proving that any given descendant may be constructed by starting from a finite set of genes and introducing the required cubic crackers through the use of six special operations, called breeding operations. It shows that each breeding operation is invertible, and these inverse operations are examined. It is therefore possible, for any given descendant, to identify a family of genes that could be used to generate the descendant. The authors refer to such a family of genes as a "complete family of ancestor genes" for that particular descendant. The book proves the fundamental, although quite unexpected, result that any given descendant has exactly one complete family of ancestor genes. This result indicates that the particular combination of breeding operations used strikes the right balance between ensuring that every descendant may be constructed while permitting only one generating set. The result that any descendant can be constructed from a unique set of ancestor genes indicates that most of the structure in the descendant has been, in some way, inherited from that, very special, complete family of ancestor genes, with the remaining structure induced by the breeding operations. After establishing this, the authors proceed to investigate a number of graph theoretic properties: Hamiltonicity, bipartiteness, and planarity, and prove results linking properties of the descendant to those of the ancestor genes. They develop necessary (and in some cases, sufficient) conditions for a descendant to contain a property in terms of the properties of its ancestor genes. These results motivate the development of parallelizable heuristics that first decompose a graph into ancestor genes, and then consider the genes individually. In particular, they provide such a heuristic for the Hamiltonian cycle problem. Additionally, a framework for constructing graphs with desired properties is developed, which shows how many (known) graphs that constitute counterexamples of conjectures could be easily found
Language
eng
Work
Publication
Extent
1 online resource.
Contents
  • Genetic Theory for Cubic Graphs
  • Inherited Properties of Descendants
  • Uniqueness of Ancestor Genes
  • Completed Proofs from Chapter 3
Isbn
9783319196800
Link
https://ezproxy.lib.ou.edu/login?url=http://link.springer.com/10.1007/978-3-319-19680-0
Instance
Label
Genetic theory for cubic graphs
Title
Genetic theory for cubic graphs
Statement of responsibility
Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe
Creator
Contributor
Author
Subject
Genre
Language
eng
Summary
This book was motivated by the notion that some of the underlying difficulty in challenging instances of graph-based problems (e.g., the Traveling Salesman Problem) may be "inherited" from simpler graphs which "in an appropriate sense" could be seen as "ancestors" of the given graph instance. The authors propose a partitioning of the set of unlabeled, connected cubic graphs into two disjoint subsets named genes and descendants, where the cardinality of the descendants dominates that of the genes. The key distinction between the two subsets is the presence of special edge cut sets, called cubic crackers, in the descendants. The book begins by proving that any given descendant may be constructed by starting from a finite set of genes and introducing the required cubic crackers through the use of six special operations, called breeding operations. It shows that each breeding operation is invertible, and these inverse operations are examined. It is therefore possible, for any given descendant, to identify a family of genes that could be used to generate the descendant. The authors refer to such a family of genes as a "complete family of ancestor genes" for that particular descendant. The book proves the fundamental, although quite unexpected, result that any given descendant has exactly one complete family of ancestor genes. This result indicates that the particular combination of breeding operations used strikes the right balance between ensuring that every descendant may be constructed while permitting only one generating set. The result that any descendant can be constructed from a unique set of ancestor genes indicates that most of the structure in the descendant has been, in some way, inherited from that, very special, complete family of ancestor genes, with the remaining structure induced by the breeding operations. After establishing this, the authors proceed to investigate a number of graph theoretic properties: Hamiltonicity, bipartiteness, and planarity, and prove results linking properties of the descendant to those of the ancestor genes. They develop necessary (and in some cases, sufficient) conditions for a descendant to contain a property in terms of the properties of its ancestor genes. These results motivate the development of parallelizable heuristics that first decompose a graph into ancestor genes, and then consider the genes individually. In particular, they provide such a heuristic for the Hamiltonian cycle problem. Additionally, a framework for constructing graphs with desired properties is developed, which shows how many (known) graphs that constitute counterexamples of conjectures could be easily found
Member of
Cataloging source
N$T
http://library.link/vocab/creatorName
Baniasadi, Pouya
Dewey number
511.5
Index
index present
LC call number
QA166.243
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorDate
1949-
http://library.link/vocab/relatedWorkOrContributorName
  • Ežov, Vladimir V.
  • Filar, Jerzy A.
  • Haythorpe, Michael
Series statement
Springer briefs in operations research
http://library.link/vocab/subjectName
  • Graph connectivity
  • Graph theory
  • MATHEMATICS
  • Graph connectivity
  • Graph theory
  • Business and Management
  • Operation Research/Decision Theory
  • Operations Research, Management Science
  • Graph Theory
  • Operational research
  • Combinatorics & graph theory
Label
Genetic theory for cubic graphs, Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe
Link
https://ezproxy.lib.ou.edu/login?url=http://link.springer.com/10.1007/978-3-319-19680-0
Instantiates
Publication
Copyright
Antecedent source
unknown
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
Genetic Theory for Cubic Graphs -- Inherited Properties of Descendants -- Uniqueness of Ancestor Genes -- Completed Proofs from Chapter 3
Dimensions
unknown
Extent
1 online resource.
File format
unknown
Form of item
online
Isbn
9783319196800
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
c
Note
SpringerLink
Other control number
10.1007/978-3-319-19680-0
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
  • (OCoLC)914165910
  • (OCoLC)ocn914165910
Label
Genetic theory for cubic graphs, Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe
Link
https://ezproxy.lib.ou.edu/login?url=http://link.springer.com/10.1007/978-3-319-19680-0
Publication
Copyright
Antecedent source
unknown
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
Genetic Theory for Cubic Graphs -- Inherited Properties of Descendants -- Uniqueness of Ancestor Genes -- Completed Proofs from Chapter 3
Dimensions
unknown
Extent
1 online resource.
File format
unknown
Form of item
online
Isbn
9783319196800
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
c
Note
SpringerLink
Other control number
10.1007/978-3-319-19680-0
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
  • (OCoLC)914165910
  • (OCoLC)ocn914165910

Subject

Genre

Member of

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

Library Links

Zepheira Logo
Structured data from the Bibframe namespace is licensed under the Creative Commons Attribution 4.0 International License by University of Oklahoma Libraries. Additional terms may apply to data associated with third party namespaces.
Processing Feedback ...