English
Español
Português (Brasil)
Toggle navigation
Digital Repository
Browse
Communities and collections
By Issue Date
Author
Title
Subject
Type
About
About
General statistics
Instructions for authors
Policy
Help
Contact Us
Help
English
English
español
português (Brasil)
English
English
español
português (Brasil)
Login
Toggle navigation
A-
A
A+
View Item
Lume Home
Academic and Technical Works
Technical and Research Reports
Technical and Research Reports
View Item
Lume Home
Academic and Technical Works
Technical and Research Reports
Technical and Research Reports
View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
Maximum matching with ordering constraints is NP-complete
View/
Open
Texto completo (289.1Kb)
Date
2009
Author
Ritt, Marcus Rolf Peter
Type
Technical and Research Report
URI
http://hdl.handle.net/10183/126651
Other options
Show all item metadata
Statistics
Subject
Grafos
Gramatica : Grafos
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.
Collections
Technical and Research Reports
(245)
Technical and Research Reports
(245)
Other options
Show all item metadata
Statistics
This item is licensed under a
Creative Commons License
Search Lume
This Collection
Lume Digital Repository
About
General statistics
Instructions for authors
Policy
Help
Browse
All of Lume
Communities and collections
By Issue Date
Author
Title
Subject
Type
This Collection
By Issue Date
Author
Title
Subject
Type
My Account
Login
Register
Share
Facebook
Google+
Twitter
LinkedIn
E-mail