COROLLARY 9. An m • n (0, 1)-matrix

COROLLARY 9. An m • n (0, 1)-matrix specified by its f nonzero entries can be
tested for circular ones in O(m + n + f) steps.
Proof. By Lemma 8 the computation of M c is within the desired time bound.
The number of edges in M c is f' ~ 2f which is O(f). The rest of the work is just
the consecutive ones test so the total work is O(m + n + f). |
There are a number of generalizations for the consecutive ones property, including
some NP-complete problems associated with finding matrices which approximate
these properties. Further related results are surveyed in [3].

ผลลัพธ์ (ไทย) 1:

COROLLARY 9 ตัว m • n (0, 1) -เมทริกซ์ที่ระบุไว้ในรายการของค่า f สามารถทดสอบในขั้นตอน O (m + n + f) สำหรับวงกลมหลักฐาน โดย 8 หน่วยการ คำนวณของ M c ได้ภายในเวลาที่ต้องการผูกมีจำนวนขอบที่ M c f' ~ ชั้น 2 ซึ่งเป็น O(f) ส่วนเหลือของการทำงานเพียงแค่คนติดต่อกันทดสอบเพื่อให้การทำงานทั้งหมด O (m + n + f) |มีจำนวนของเดิม ๆ สำหรับติดต่อที่พัก รวมถึงปัญหาสอบเกี่ยวข้องกับค้นหาเมทริกซ์ซึ่งใกลเคียงคุณสมบัติเหล่านี้ เพิ่มเติม การได้รับการสำรวจผลเกิดใน [3]

ผลลัพธ์ (ไทย) 2:

ควันหลง 9. เมตร• n (0, 1) -matrix ระบุโดยรายการภัณฑ์ของ F สามารถ
ทดสอบสำหรับคนที่วงกลมใน O (m + n + F) ขั้นตอน.
หลักฐาน โดยแทรก 8 คำนวณเอ็มซีอยู่ในเวลาที่ต้องการผูกพัน.
จำนวนขอบในเอ็ม C คือ F '~ 2f ซึ่งเป็น O (F) ส่วนที่เหลือของการทำงานเป็นเพียง
การทดสอบคนที่ติดต่อกันเพื่อให้การทำงานรวมเป็น O (m + n + F) |
มีจำนวนของภาพรวมสำหรับคนที่ติดต่อกันทรัพย์สินรวมถึงมี
บางปัญหาเอ็นพีบริบูรณ์ที่เกี่ยวข้องกับการหาเมทริกซ์ซึ่งตัวอย่าง
คุณสมบัติเหล่านี้ ผลลัพธ์ที่เกี่ยวข้องต่อไปจะสำรวจใน [3]

ผลลัพธ์ (ไทย) 3:

ควันหลง 9 ตัว M - N ( 0 , 1 ) - เมทริกซ์ที่ระบุโดย F 0 รายการ สามารถทดสอบวงกลมอยู่ใน O ( M + N + F ) ขั้นตอนพิสูจน์ โดยแทรก 8 การคำนวณของ M C ภายในเวลาที่ต้องการผูกไว้จำนวนของขอบใน M C F " ~ ห้อง 2F ซึ่งเป็น O ( F ) ส่วนที่เหลือของงานคือการติดต่อกันที่ทดสอบดังนั้นงานทั้งหมดคือ O ( M + N + F ) |มีจำนวนของทั่วไปสำหรับคุณสมบัติที่ติดต่อกัน รวมถึงบางปัญหาที่เกี่ยวข้องกับการค้นหา NP สมบูรณ์เมทริกซ์ซึ่งโดยประมาณคุณสมบัติเหล่านี้ เพิ่มเติมที่เกี่ยวข้องกับผลการสำรวจใน [ 3 ]