Texas A&M University LibrariesTexas A&M University LibrariesTexas A&M University Libraries
    • Help
    • Login
    OAKTrust
    View Item 
    •   OAKTrust Home
    • Colleges and Schools
    • Office of Graduate and Professional Studies
    • Electronic Theses, Dissertations, and Records of Study (2002– )
    • View Item
    •   OAKTrust Home
    • Colleges and Schools
    • Office of Graduate and Professional Studies
    • Electronic Theses, Dissertations, and Records of Study (2002– )
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem

    Thumbnail
    View/Open
    etd-tamu-2004C-INEN-sachdeva.pdf (1.668Mb)
    Date
    2006-04-12
    Author
    Sachdeva, Sandeep
    Metadata
    Show full item record
    Abstract
    We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.
    URI
    http://hdl.handle.net/1969.1/3251
    Subject
    integer programming
    Branch and Price
    maximum weighted independent set problem
    partitioning
    vertex cloning
    Collections
    • Electronic Theses, Dissertations, and Records of Study (2002– )
    Citation
    Sachdeva, Sandeep (2004). Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem. Master's thesis, Texas A&M University. Texas A&M University. Available electronically from http : / /hdl .handle .net /1969 .1 /3251.

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Advanced Search

    Browse

    All of OAKTrustCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDepartmentThis CollectionBy Issue DateAuthorsTitlesSubjectsDepartment

    My Account

    LoginRegister

    Statistics

    View Usage Statistics
    Help and Documentation

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV