The Rectilinear Steiner Arborescence Problem Is NP-Complete.

Weiping Shi Chen Su

Published in: SIAM J. Comput. (2005)

Keyphrases

np complete
np hard
computational complexity
satisfiability problem
randomly generated
pspace complete

minimum weight
constraint satisfaction problems
d mesh
conjunctive queries
phase transition

arbitrary shaped
np complete problems
special case
lower bound
bounded treewidth

polynomial time complexity
relational databases
real time
sat problem
minimum spanning tree