Some complexity results about threshold graphs

The problem of determining whether a graph G contains a threshold subgraph containing at least h edges is shown to be NP-complete if h is part of the input as the problems of minimum threshold completion, weighted 2-threshold partition and weighted 2-threshold covering. We also prove that the k-cyclic scheduling problem is NP-complete for all fixed k, a result used to show that deciding whether a threshold r-hypergraph contains a Hamiltonian cycle is NP-complete


Published in:
Discrete Applied Mathematics, 49, 299-308
Year:
1994
Note:
PRO 94.03
Laboratories:




 Record created 2006-02-13, last modified 2018-01-27


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)