A LINEAR PROGRAMMING RELAXATION OF THE NODE PACKING PROBLEM OR 2-BICRITICALGRAPHS AND NODE COVERS

Simple item page
dc.contributor.authorPulleyblank, William R.eng
dc.date.accessioned2008-02-26T22:41:17Z
dc.date.available2008-02-26T22:41:17Z
dc.date.computerscience1999-05-27eng
dc.date.issued1978-03-01eng
dc.description.abstractThe problem of finding a minimum cardinality set of nodes in a graph which meet every edge is of considerable theoretical as well as practical interest. Because of the difficulty of this problem, a linear relaxation of an integer programming model is sometimes used as a heuristic. In fact Nemhauser and Trotter showed that any variables which receive integer values in an optimal solution to the relaxation can retain the same values in an optimal solution to the integer program. We define 2-bicritical graphs and give several characterizations of them. One characterization is that they are precisely the graphs for which an optimal solution to the linear relaxation will have no integer valued variables. Then we show that almost all graphs are 2-bicritical, and hence the linear relaxation almost never helps.eng
dc.description.notesWe are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.caeng
dc.identifier.department1978-23-2eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/30965
dc.identifier.urihttp://hdl.handle.net/1880/45609
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleA LINEAR PROGRAMMING RELAXATION OF THE NODE PACKING PROBLEM OR 2-BICRITICALGRAPHS AND NODE COVERSeng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.86 KB
Format:
Plain Text
Description:
Download
Collections
Science Research & Publications