Name
Abstract | ||
|---|---|---|
Let Q c , r be the integer hull of the intersection of the assignment polytope with a given hyper-plane H = { x = ( x ij ) ϵ R n × n : ∑ n i = 1 ∑ n j = 1 c ij x ij = r }. We show that the problem of checking whether two given extreme points of Q c , r are nonadjacent on Q c , r is solvable in O (n 5 ) time if c = ( c ij ) is a 0–1 matrix, and that it is NP-Complete if c is a general integer matrix. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0166-218X(98)00063-8 | Discrete Applied Mathematics |
Keywords | Field | DocType |
computational complexity,integer hull,adjacency checking,constrained assignment problem,assignment problem,extreme point,combinatorial optimization | Integer,Adjacency list,Extreme point,Discrete mathematics,Combinatorics,Matrix (mathematics),Polytope,Assignment problem,Integer matrix,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
87 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abdo Y. Alfakih | 1 | 103 | 11.35 |
| Katta G. Murty | 2 | 602 | 95.15 |