• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 6 публикаций
Сортировка:
по названию
по году
Статья
Gurvich V., Boros E., Manthey B. et al. Algorithmica. 2018. Vol. 80. No. 11. P. 3132-3157.
Добавлено: 2 ноября 2017
Статья
Babenko M. A. Algorithmica. 2012. Vol. 64. No. 3. P. 362-383.

Пусть задан орграф $G = (VG,AG)$. Четным фактором $M \subseteq AG$ называется множество ребер, образованное набором вершинно непересекающихся путей и четных циклов. Четные факторы были введены Гиленом и Каннингхемом, они обобщают т.н. path matchings в неориентированных графах. Задача нахождения четного фактора максимального размера в графе общего вида является NP-трудной, однако для класса  нечетно циклически симметричных орграфов эта задача является полиномиальной.  К настоящему моменту был известен лишь один комбинаторный способ ее решения, принадлежащий Папу. Этот алгоритм имеет сложность  $O(n^4)$ (где $n$ обозначает число вершин в $G$, а $m$ обозначает число ребер). В данной работе мы развиваем новую технику разреженного восстановления и строим алгоритм со сложностью $O(n^3 \log n)$, находящий нечетный фактор максимального размера в нечетно циклически симметричном орграфе. Наш подход также применим к другим аналогичным задачам, например к задаче нахождения максимального простого $b$-паросочетания без квадратов.

Добавлено: 27 января 2013
Статья
Bliznets Ivan, Fomin F., Pilipczuk M. et al. Algorithmica. 2016. Vol. 76. No. 2. P. 569-594.
Добавлено: 26 октября 2018
Статья
Bliznets Ivan, Fomin F., Golovach P. et al. Algorithmica. 2017. Vol. 79. No. 3. P. 798-813.
Добавлено: 29 октября 2018
Статья
Buhrman H., Torenvliet L., Unger F. et al. Algorithmica. 2019. Vol. 81. No. 1. P. 179-200.
Добавлено: 12 сентября 2018
Статья
Brody J., Buhrman H., Koucký M. et al. Algorithmica. 2016. Vol. 76. No. 3. P. 749-781.
Добавлено: 2 марта 2016