نهج إرشادي لمشكلة C1S
DOI:
https://doi.org/10.21123/bsj.2022.6373الكلمات المفتاحية:
تصغير الكتل المتتالية, خاصية الواحدات متتالية,مصفوفة الواحدات المتتالية الفرعية, أدراج العمود, استدلالالملخص
أعطيت مصفوفة (0،1)، تم اقتراح مسألة المصفوفة الجزئية ذات الواحدات المتعاقبة والتي تهدف إلى إيجاد تبديل للأعمدة التي تزيد من عدد الأعمدة التي تحتوي معًا على قالب واحد فقط من الواحدات المتعاقبة في كل صف. سيتم اقتراح اسلوب الاستدلال لحل المسألة. كما سيتم دراسة مسألة تقليل القوالب المتتالية ذات الصلة بمسألة المصفوفة الجزئية ذات الواحدات المتعاقبة. تم اقتراح اجراء جديد لتحسين طريقة إدراج العمود. يتم بعد ذلك تقييم مصفوفات العالم الحقيقي ومصفوفات متولدة عشوائيًا من مسألة غطاء المجموعة و تعرض النتائج الحسابية.
Received 26/5/2021
Accepted 3/4/2022
Published Online First 20/7/2022
المراجع
Fulkerson D, Gross O. Incidence matrices and interval graphs. Pac J Math. 1965; 15(3): 835-855.
Haddadi S, Chenche S, Cheraitia M, Guessoum F. Polynomial time local-improvement algorithm for consecutive block minimization. Inf Process Lett. 2015; 115(6): 612-617.
Tan J, Zhang L. The consecutive ones submatrix problem for sparse matrices. Algorithmica. 2007; 48(3): 287-299.
Dom M, Guo J, Niedermeier R. Approximation and fixed-parameter algorithms for consecutive ones submatrix problems. J Comput Syst Sci. 2010; 76(3): 204-221.
Tucker A A structure theorem for the consecutive 1's property. J Comb Theory Ser B. 1972; 12(2): 153-162.
Safe MD. Circularly compatible ones, d-circularity, and proper circular-arc bigraphs. arXiv preprint arXiv. 1906.00321. 2019.
Pardal N. Structural characterization of some problems on circle and interval graphs. arXiv preprint arXiv. 2006.00099, 2020.
Safe MD. Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property. J Graph Theory. 2020; 93(2): 268-298.
Pardal N, Durán GA, Grippo LN, Safe MD, On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs. arXiv preprint arXiv. 1906.11970, 2019.
Cao Y, Grippo LN, Safe MD. Forbidden induced subgraphs of normal helly circular-arc graphs: Characterization and detection. Discret Appl Math. 2017;216:67-83.
De Luca F, Hossain MI, Kobourov S, Lubiw A, Mondal D. Recognition and drawing of stick graphs. Theor Comput Sci. 2019; 796:22-33.
Meidanis J, Porto O, Telles GP. On the consecutive ones property. Discrete Appl Math. 1998; 88(1): 325-354.
Booth KS, Lueker GS. Testing for the consecutive ones property, interval graphs, and gr aph planarity using PQ-tree algorithms. J Comput Syst Sci. 1976; 13(3): 335-379.
Hajiaghayi MT, Ganjali Y. A note on the consecutive ones submatrix problem. Inf Process Lett. 2002; 83(3): 163-166.
Haddadi S. Benders decomposition for set covering problems. J Comb Optim. 2017; 33(1): 60-80.
Soares LC, Reinsma JA, Nascimento LH, Carvalho MA. Heuristic methods to consecutive block minimization. Comput Oper Res. 2020; 120: 104948.
Abo-Alsabeh R, Salhi A. A Metaheuristic approach to the C1S problem. Iraqi J Sci. 2021; 62 (1): 218-227.
Subashini R, Rani MR, Jagalmohanan M.Simultaneous consecutive ones submatrix and editing problems: Classical complexity and fixed-parameter tractable results. Theor Comput Sci. 2020; 812: 13-38.
Kendall D. Incidence matrices, interval graphs and seriation in archaeology. Pac J Math. 1969; 28(3): 565-570.
Abduljabbar IA, Abdullah SM. An Evolutionary Algorithm for Solving Academic Courses Timetable Scheduling Problem. Baghdad Sci J. 2022; 19(2): 0399-0399.
Iqbal Z, Ilyas R, Chan HY, Ahmed N. Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach. Baghdad Sci J. 2021; 18(4): 1465-1465.
Ruf N, Scho ̈bel AA. Set covering with almost consecutive ones property. Discrete Optim. 2004; 1(2): 215-228.
التنزيلات
منشور
إصدار
القسم
الرخصة
الحقوق الفكرية (c) 2022 مجلة بغداد للعلوم
هذا العمل مرخص بموجب Creative Commons Attribution 4.0 International License.
كيفية الاقتباس
