Fulkerson and Gross published an O(

Fulkerson and Gross published an O(mn ~) algorithm for testing an m • n matrix
for the consecutive ones property [8]. This bound can be improved by noticing
that the dominant term is due to the computation of a matrix product. Using the
techniques developed by Strassen [28], the Fulkerson-Gross algorithm can be implemented
to run in O(max{m(l~ 2, mnO~ steps for an m • n (0, 1)-matrix
[3]. Using the reduction algorithm an even better bound can be obtained. The basic
algorithm is the following procedure.

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

Fulkerson และรวมการเผยแพร่อัลกอริทึมสำหรับการทดสอบเมทริกซ์ n •การ m O(mn ~)สำหรับการติดต่อคนคุณสมบัติ [8] นี้ผูกไว้สามารถแก้ไขได้ โดยการสังเกตเห็นที่คำหลักได้เนื่องจากการคำนวณของผลิตภัณฑ์ matrix โดยใช้การสามารถดำเนินการเทคนิคที่พัฒนา โดยอัลกอริทึมรวม Fulkerson Strassen [28],การเรียกใช้ใน O (สูงสุด { m(l~ 2, mnO~ steps for an m • n (0, 1)-เมตริกซ์[3] . ใช้อัลกอริทึมลดการผูกยิ่งได้ พื้นฐานอัลกอริทึมเป็นกระบวนการต่อไปนี้

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

Fulkerson และมวลรวมการตีพิมพ์เป็น O (ล้าน ~) อัลกอริทึมสำหรับการทดสอบเมตร• n เมทริกซ์
สำหรับคนที่ติดต่อกันคุณสมบัติ [8] ผูกพันนี้สามารถปรับปรุงโดยสังเกตเห็น
ว่าในระยะที่โดดเด่นคือเนื่องจากการคำนวณของผลิตภัณฑ์เมทริกซ์ โดยใช้
เทคนิคการพัฒนาโดย Strassen [28], อัลกอริทึม Fulkerson-Gross สามารถดำเนินการ
เพื่อให้ทำงานใน O (สูงสุด {m (L ~ 2 ~ MNO ขั้นตอนสำหรับเมตร• n (0, 1) -matrix
[3] โดยใช้วิธีการลดยิ่งผูกพันที่ดีขึ้นสามารถรับได้. พื้นฐาน
ขั้นตอนวิธีการเป็นขั้นตอนต่อไป

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

Fulkerson และรวมตีพิมพ์ O ( MN ) ขั้นตอนวิธีการทดสอบ M - N เมทริกซ์สำหรับคนที่ติดต่อกันคุณสมบัติ [ 8 ] ผูกพันนี้สามารถปรับปรุงได้ โดยการสังเกตว่าระยะเด่นเนื่องจากการคำนวณของผลิตภัณฑ์เมตริกซ์ โดยใช้เทคนิคที่พัฒนาขึ้นโดย strassen [ 28 ] , Fulkerson ขั้นตอนวิธีที่สามารถดำเนินการรวมทำงานใน O ( Max { M ( L ~ 2 ขั้นตอนรูป ~ เป็น M - N ( 0 , 1 ) - เมทริกซ์[ 3 ] การลดขั้นตอนวิธียิ่งขึ้นผูกพันสามารถรับ พื้นฐานวิธีการเป็นขั้นตอนดังต่อไปนี้