Моделирование алгоритма вычисления граничного ранга матрицы на основе построения двудольного графа в среде MATLAB
Автор: Фам Л.Х.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 4 (48) т.12, 2020 года.
Бесплатный доступ
Рассматривается метод вычисления граничного ранга матрицы на основе построения двудольного графа. Граничным рангом двоичной матрицы называется минимальное число строк и столбцов, в которых содержатся все ненулевые элементы матрицы. В данной работе речь пойдет о алгоритме Форда-Фулкерсона для задачи максимального потока. Далее предлагается моделирование алгоритма в среде MATLAB. Рассматривается приложение этого алгоритма для оценки характеристики кодов в гранично-ранговой метрике.
Граничный ранг, решетчатые конструкции, блоковый код, двудольный граф, алгоритм форда-фулкерсона
Короткий адрес: https://sciup.org/142229696
IDR: 142229696
Список литературы Моделирование алгоритма вычисления граничного ранга матрицы на основе построения двудольного графа в среде MATLAB
- Габидулин Э.М. Оптимальные коды, исправляющие ошибки решетчатой конфигурации // Пробл. передачи информ. 1985. Т. 21, вып. 2. С. 103-108.
- Фам Л.Х. Алгоритм вычисления граничного ранга двоичной матрицы // Труды МФТИ. 2019. Т. 11, № 1. С. 62-68.
- Альпин Ю.А., Ильин С.Н. Дискретная математика: графы и автоматы. Казань: Казанский государственный университет, 2006. C. 56-59.
- Konig D. Graphok es matrixok (Hungarian)[Graphs and matrices] // Matematikai es Fizikai Lapok. 1931. Т. 38. С. 116-119.
- Hopcroft J.E., Karp R.M. An n5/2 algorithm for maximum matchings in bipartite graphs // SIAM Journal on computing. 1973. Т. 2, N 4. С. 225-231.
- Ford Jr.L.R., Fulkerson D.R. Flows in networks. Princeton university press, 2015. Т. 54.
- Pham L.H. Construction of new codes in term-rank metric // IET Communications. 2020. V. 14, N 8. P. 1215-1220.
