Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
यह शोध पत्र पाँच विशिष्ट प्रकार के प्रतिबंधों के तहत कंट्रोल फ्लो ग्राफ में एज कवरेज प्राप्त करने की कम्प्यूटेशनल जटिलता की जांच करता है, यह प्रदर्शित करते हुए कि जहाँ POSITIVE प्रतिबंध बहुपद समय (polynomial time) में हल करने योग्य बने रहते हैं, वहीं NEGATIVE, ONCE, MAX ONCE, और ALWAYS प्रतिबंध इस समस्या को अचक्रीय (acyclic) ग्राफों के लिए भी NP-complete बना देते हैं, हालांकि बाद वाला प्रतिबंध बाधाओं की संख्या के संबंध में एक फिक्स्ड-पैरामीटर ट्रैक्टेबल एल्गोरिदम को स्वीकार करता है।