The Resource Genetic Theory for Cubic Graphs, by Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe, (electronic resource)

Genetic Theory for Cubic Graphs, by Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe, (electronic resource)

Label
Genetic Theory for Cubic Graphs
Title
Genetic Theory for Cubic Graphs
Statement of responsibility
by Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe
Creator
Contributor
Author
Provider
Subject
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
http://library.link/vocab/creatorName
Baniasadi, Pouya
Image bit depth
0
LC call number
HD30.23
Literary form
non fiction
http://library.link/vocab/relatedWorkOrContributorName
  • Ejov, Vladimir.
  • Filar, Jerzy A.
  • Haythorpe, Michael.
  • SpringerLink
Series statement
SpringerBriefs in Operations Research,
http://library.link/vocab/subjectName
  • Business
  • Operations research
  • Decision making
  • Management science
  • Graph theory
  • Business and Management
  • Operation Research/Decision Theory
  • Operations Research, Management Science
  • Graph Theory
Label
Genetic Theory for Cubic Graphs, by Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe, (electronic resource)
Instantiates
Publication
Antecedent source
mixed
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
not applicable
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
X, 118 p. 85 illus., 8 illus. in color.
File format
multiple file formats
Form of item
electronic
Isbn
9783319196800
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other control number
10.1007/978-3-319-19680-0
Other physical details
online resource.
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
(DE-He213)978-3-319-19680-0
Label
Genetic Theory for Cubic Graphs, by Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe, (electronic resource)
Publication
Antecedent source
mixed
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
not applicable
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
X, 118 p. 85 illus., 8 illus. in color.
File format
multiple file formats
Form of item
electronic
Isbn
9783319196800
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other control number
10.1007/978-3-319-19680-0
Other physical details
online resource.
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
(DE-He213)978-3-319-19680-0

Library Locations

  • African Studies LibraryBorrow it
    771 Commonwealth Avenue, 6th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Alumni Medical LibraryBorrow it
    72 East Concord Street, Boston, MA, 02118, US
    42.336388 -71.072393
  • Astronomy LibraryBorrow it
    725 Commonwealth Avenue, 6th Floor, Boston, MA, 02445, US
    42.350259 -71.105717
  • Fineman and Pappas Law LibrariesBorrow it
    765 Commonwealth Avenue, Boston, MA, 02215, US
    42.350979 -71.107023
  • Frederick S. Pardee Management LibraryBorrow it
    595 Commonwealth Avenue, Boston, MA, 02215, US
    42.349626 -71.099547
  • Howard Gotlieb Archival Research CenterBorrow it
    771 Commonwealth Avenue, 5th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Mugar Memorial LibraryBorrow it
    771 Commonwealth Avenue, Boston, MA, 02215, US
    42.350723 -71.108227
  • Music LibraryBorrow it
    771 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Pikering Educational Resources LibraryBorrow it
    2 Silber Way, Boston, MA, 02215, US
    42.349804 -71.101425
  • School of Theology LibraryBorrow it
    745 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350494 -71.107235
  • Science & Engineering LibraryBorrow it
    38 Cummington Mall, Boston, MA, 02215, US
    42.348472 -71.102257
  • Stone Science LibraryBorrow it
    675 Commonwealth Avenue, Boston, MA, 02445, US
    42.350103 -71.103784
Processing Feedback ...