Geodesic
Defragmentation of permutation tables with four columns
Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 95-104.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a table with columns each of which contains each symbol of an alphabet $A$ precisely once; the remaining elements of a column are equal to zero. It is required to transform the table preserving the sets of elements in each row and each column to the form with consecutively placed elements of alphabet $A$ in each row. We give conditions for solvability of this problem. 
@article{DM_2009_21_4_a8,
     author = {A. M. Magomedov},
     title = {Defragmentation of permutation tables with four columns},
     journal = {Diskretnaya Matematika},
     pages = {95--104},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_4_a8/}
}
TY  - JOUR
AU  - A. M. Magomedov
TI  - Defragmentation of permutation tables with four columns
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 95
EP  - 104
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_4_a8/
LA  - ru
ID  - DM_2009_21_4_a8
ER  - 
%0 Journal Article
%A A. M. Magomedov
%T Defragmentation of permutation tables with four columns
%J Diskretnaya Matematika
%D 2009
%P 95-104
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2009_21_4_a8/
%G ru
%F DM_2009_21_4_a8
A. M. Magomedov. Defragmentation of permutation tables with four columns. Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 95-104. http://geodesic.mathdoc.fr/item/DM_2009_21_4_a8/

[1] Even S., Itai A., Shamir A., “On the complexity of timetable and multicommodity flow problems”, SIAM J. Comp., 5:4 (1976), 691–703 | DOI | MR | Zbl

[2] Magomedov A. M., “Defragmentatsiya tablits perestanovok s sokhraneniem naborov elementov v liniyakh”, Tez. dokl. 14 Mezhdunarodnoi konf. “Problemy teoreticheskoi kibernetiki”, Izd-vo mekh.-mat. f-ta MGU, Moskva, 2005, 92

[3] Booth K. S., Lueker G. S., “Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms”, J. Comput. Syst. Sci., 13 (1976), 335–379 | MR | Zbl

[4] Hajiagayi M. T., Ganjali Y., “A note on the consecutive ones submatrix problem”, Inform. Process. Lett., 83 (2002), 163–166 | DOI | MR

[5] Magomedov A. M., “Defragmentatsiya matritsy perestanovok v nekotorykh chastnykh sluchayakh”, Materialy Mezhdunarodnogo seminara “Diskretnaya matematika i prilozheniya”, posvyaschennogo pamyati akad. O. B. Lupanova, Izd-vo MGU, Moskva, 2007, 200

[6] Magomedov A. M., “Razmeschenie nedelimykh 2-slov v matritse kak zadacha faktorizatsii grafa”, Vestnik Dagestanskogo nauchnogo tsentra, 23 (2006), 5–14

[7] Petersen J., “Die Theorie der regulären Graphen”, Acta Math., 15 (1891), 193–220 | DOI | MR

[8] Ford L. R., Falkerson D. R., Potoki v setyakh, Mir, Moskva, 1963