Geodesic
Successive partition of edges of bipartite graph into matchings
Diskretnaya Matematika, Tome 28 (2016) no. 1, pp. 78-86.

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

It is assumed that the input data for scheduling a set of customers are given as a bipartite graph in some system of units. We consider the problem of composing a schedule of smallest length under the condition of continuous work with no downtime of each unit and their simultaneous actuation. Conditions are obtained for a partition of the edge set of a graph into matchings to form a schedule of the required form.
Keywords: graph, schedule, bipartite graph, matching, queuing. 
@article{DM_2016_28_1_a3,
     author = {A. M. Magomedov and T. A. Magomedov},
     title = {Successive partition of edges of bipartite graph into matchings},
     journal = {Diskretnaya Matematika},
     pages = {78--86},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_1_a3/}
}
TY  - JOUR
AU  - A. M. Magomedov
AU  - T. A. Magomedov
TI  - Successive partition of edges of bipartite graph into matchings
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 78
EP  - 86
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_1_a3/
LA  - ru
ID  - DM_2016_28_1_a3
ER  - 
%0 Journal Article
%A A. M. Magomedov
%A T. A. Magomedov
%T Successive partition of edges of bipartite graph into matchings
%J Diskretnaya Matematika
%D 2016
%P 78-86
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_1_a3/
%G ru
%F DM_2016_28_1_a3
A. M. Magomedov; T. A. Magomedov. Successive partition of edges of bipartite graph into matchings. Diskretnaya Matematika, Tome 28 (2016) no. 1, pp. 78-86. http://geodesic.mathdoc.fr/item/DM_2016_28_1_a3/

[1] Svami M., Tkhulasiraman K., Grafy, seti i algoritmy, Mir, M., 1982; Swamy M. N. S., Thulasiraman K., Graphs, Networks, and Algorithms, Wiley, 1981, 592 pp. | MR | Zbl

[2] Vizing V. G., “Ob otsenke khromaticheskogo klassa $p$-grafa”, Diskretnyi analiz, Sb. nauch. tr., v. 3, In-t matematiki SO AN SSSR, Novosibirsk, 1964, 25–30 | MR

[3] Holyer I., “The NP-completeness of edge-coloring”, SIAM J. Comput., 10:4 (1981), 718–720 | DOI | MR | Zbl

[4] Lovas L., Plammer M., Prikladnye zadachi teorii grafov. Teoriya parosochetanii v matematike, fizike, khimii, Mir, M., 1998; Lovász L., Plummer M.D., Matching theory, North-Holland, 1986, 544 pp. | MR | Zbl

[5] Asratyan A. S., Kamalyan R. R., “Intervalnye raskraski reber multigrafa”, Prikladnaya matematika, 5 (1987), 25–34, Izd-vo Erevanskogo un-ta, Erevan | MR

[6] Magomedov A. M., “Nepreryvnoe raspisanie dlya spetsializirovannykh protsessorov bez otnosheniya predshestvovaniya”, Vestnik MEI, ser. Avtomatika, vychisl. tekhnika, informatika, 5 (2009), 14–17

[7] Magomedov A. M., Sapozhenko A. A., “Usloviya suschestvovaniya nepreryvnykh raspisanii dlitelnosti pyat”, Vestnik MGU, ser. Vychisl. matem. i kibernetika, 34:1 (2010), 39–44 | MR | Zbl

[8] Magomedov A. M., Magomedov T. A., “O prilozhenii algoritma vychisleniya podgrafa maksimalnoi plotnosti k zadache optimizatsii raspisaniya”, Matem. zametki, 93:2 (2013), 313–315 | DOI | MR | Zbl

[9] Magomedov A. M., “Nepreryvnoe uchebnoe raspisanie s $m$, $m-2$ ili 2 urokami u prepodavatelei”, Diskretnaya matematika, 24:2 (2012), 37–45 | DOI | MR | Zbl