dc.date.accessioned | 2013-03-12T08:01:31Z | |
dc.date.available | 2013-03-12T08:01:31Z | |
dc.date.issued | 1997 | en_US |
dc.date.submitted | 2006-11-27 | en_US |
dc.identifier.uri | http://hdl.handle.net/10852/9573 | |
dc.description.abstract | Given a graph G with a specified root node r. A spanning tree in G where each node has distance at most 2 from r is called a 2-hop spanning tree. For given edge weights the 2-hop spanning tree problem is to find a minimum weight 2-hop spanning tree. The problem is NP-hard and has some interesting applications. We study a polytope associated with a directed model of the problem give a completeness result for wheels and a vertex description of a linear relaxation. Some classes of valid inequalities for the convex hull of incidence vectors of 2-hop spanning trees are derived by projection techniques. | nor |
dc.language.iso | eng | en_US |
dc.relation.ispartof | Research report http://urn.nb.no/URN:NBN:no-35645 | en_US |
dc.relation.uri | http://urn.nb.no/URN:NBN:no-35645 | |
dc.title | The 2-hop spanning tree problem | en_US |
dc.type | Research report | en_US |
dc.date.updated | 2006-12-01 | en_US |
dc.creator.author | Dahl, Geir | en_US |
dc.subject.nsi | VDP::420 | en_US |
dc.identifier.urn | URN:NBN:no-13704 | en_US |
dc.type.document | Forskningsrapport | en_US |
dc.identifier.duo | 49389 | en_US |
dc.identifier.bibsys | 061918407 | en_US |
dc.identifier.fulltext | Fulltext https://www.duo.uio.no/bitstream/handle/10852/9573/1/GDahl-3.pdf | |