Maximum matching with ordering constraints is NP-complete

dc.contributor.author	Ritt, Marcus Rolf Peter	pt_BR
dc.date.accessioned	2015-09-14T15:57:39Z	pt_BR
dc.date.issued	2009	pt_BR
dc.identifier.uri	http://hdl.handle.net/10183/126651	pt_BR
dc.description.abstract	A maximum weighted matching in a graph can be computed in polynomial time. In this paper we show that a variant, where the matching lias to respect additional ordering constraints between the vertices makes the problem NP-complete.	en
dc.format.mimetype	application/pdf
dc.language.iso	eng	pt_BR
dc.rights	Open Access	en
dc.subject	Gramatica : Grafos	pt_BR
dc.subject	Grafos	pt_BR
dc.title	Maximum matching with ordering constraints is NP-complete	pt_BR
dc.type	Relatório técnico e de pesquisa	pt_BR
dc.identifier.nrb	000722872	pt_BR

This item is licensed under a Creative Commons License