On the job rotation problem



Corollary 9. Let A Tn×n be a symmetric matrix, σ1 , σ2 , . . . , σt be a collec-
tion of PND cycles in
D(A) covering kmax or kmax - 1 nodes, with at least one
having length
koddmin. Then we can decide whether δk (A) is 0 or -∞ for all k
in linear time, after finding kmax and koddmin .

Proof. The result follows from Corollary 4 and Theorem 8.

Theorem 10. If A Tn×n is a symmetric matrix, then δk (A) = 0 for all odd

k {koddmin, . . . , kmax

koddmin}.


Proof. As δkmax = 0, there exist PND cycles σ1, σ2, . . . , σt in D(A) that cover
kmax nodes. There exists a cycle σ in D(A) of length koddmin.

Delete all nodes in V (σ) from σ1, σ2, . . . , σt, as well as incident arcs. As
the cycles were PND and each node was incident to precisely two arcs, up
to 2
koddmin arcs have been deleted. Therefore this leaves a total of at least
kmax - 2koddmin arcs within the remaining PND cycles and paths that have
arisen from deleting the arcs from the cycles. Split any paths into 2-cycles.
We now have PND cycles in
D(A) covering at least kmax - 2koddmin arcs, and
therefore at least
kmax - 2koddmin nodes, none of which are nodes on σ.

Therefore, by Corollary 4, for all even i ≤ kmax - 2koddmin , there exist PND
cycles
σ10 , σ20 , . . . , σt00 in D(A) covering i nodes, but none on σ. So for all even
i ≤ kmax - 2koddmin, we have PND cycles σ10 , σ20 , . . . , σt00 and σ in D(A) which
cover
i + koddmin nodes. Hence the result.                                 □

Remark. Note that {koddmin, ∙ ∙ ∙ , kmax koddmin} = ^ ^ koddmin   2 .

Corollary 11. Let A Tn×n be a symmetric matrix, with PND cycles in
D(A) covering kmax or kmax - 1 nodes, one having odd length of at most
kmax - koddmin . Then we can decide whether δk (A) is 0 or -∞ for all k in
linear time, after finding
kmax and koddmin .

Proof. The result follows from Corollary 4, Theorem 8 and Theorem 10.    □

Corollary 12. Let A Tn×n be a symmetric matrix, with PND cycles in D(A)
covering
kmax or kmax - 1 nodes, two having odd length. Then we can decide
whether
δk (A) is 0 or -∞ for all k in linear time, after finding kmax .

Proof. The result follows from Corollary 11 and the fact that the length of at
least one of the odd cycles is at most
km2ax ≤ kmax — koddmin.               □

10



More intriguing information

1. A Multimodal Framework for Computer Mediated Learning: The Reshaping of Curriculum Knowledge and Learning
2. Self-Help Groups and Income Generation in the Informal Settlements of Nairobi
3. Assessing Economic Complexity with Input-Output Based Measures
4. The name is absent
5. Der Einfluß der Direktdemokratie auf die Sozialpolitik
6. The name is absent
7. Structural Influences on Participation Rates: A Canada-U.S. Comparison
8. The name is absent
9. REVITALIZING FAMILY FARM AGRICULTURE
10. THE EFFECT OF MARKETING COOPERATIVES ON COST-REDUCING PROCESS INNOVATION ACTIVITY