It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in[2]due to D.B.West.In this note,by extending the proof technique in[2],we briefly show that the girth of ev...It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in[2]due to D.B.West.In this note,by extending the proof technique in[2],we briefly show that the girth of every 3-regular hamiltonian graph on n≥10 vertices is at most(n+4)/3.展开更多
We study the single-machine preemptive scheduling problem with multiple maintenance activities to minimize the total late work,in which the jobs must be processed in the time space not occupied by the maintenance inte...We study the single-machine preemptive scheduling problem with multiple maintenance activities to minimize the total late work,in which the jobs must be processed in the time space not occupied by the maintenance intervals.For this problem,we present a polynomial algorithm to determine the optimal schedule and establish a formula expression to the optimal value.Moreover,our result is used to correct some minor errors in the literature related to the single-machine(preemptive or non-preemptive)scheduling with one maintenance activity to minimize the total late work.展开更多
基金Supported by National Natural Science Foundation of China(Grant No.12071442)the Fundamental Research Funds for the Central Universities under(Grant No.020314380035)。
文摘It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in[2]due to D.B.West.In this note,by extending the proof technique in[2],we briefly show that the girth of every 3-regular hamiltonian graph on n≥10 vertices is at most(n+4)/3.
基金Supported by National Natural Science Foundation of China(Grant Nos.12071442,12201186).
文摘We study the single-machine preemptive scheduling problem with multiple maintenance activities to minimize the total late work,in which the jobs must be processed in the time space not occupied by the maintenance intervals.For this problem,we present a polynomial algorithm to determine the optimal schedule and establish a formula expression to the optimal value.Moreover,our result is used to correct some minor errors in the literature related to the single-machine(preemptive or non-preemptive)scheduling with one maintenance activity to minimize the total late work.
