?
The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
Siberian Electronic Mathematical Reports. 2014. Vol. 11. P. 811–822.
We obtain a complete complexity dichotomy for the edge 3- colorability within the family of hereditary classes defined by forbidden
induced subgraphs on at most 6 vertices and having at most two 6-vertex forbidden induced structures.
Язык:
английский
Ключевые слова: hereditary class of graphsefficient algorithmedge 3-colorabilityComputational Complexity
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Association for Computational Linguistics, 2026.
Добавлено: 14 июня 2026 г.
Добавлено: 11 июня 2026 г.
Strube M., Braud C., Hardmeier C. и др., Suzhou: Association for Computational Linguistics, 2025.
Добавлено: 11 июня 2026 г.
Добавлено: 10 июня 2026 г.
Добавлено: 10 июня 2026 г.
Дистиллированные кисломолочные напитки встречаются в пищевой промышленности редко, несмотря на повсеместное распространение растительных спиртных напитков. В настоящее время производство крепких дистиллированных алкогольных напитков из кисломолочных продуктов с использованием традиционных технологий известно лишь среди монголоязычных народов и их сибирских соседей. Данное исследование представляет собой первый междисциплинарный анализ дарасуна, традиционного бурятского спиртного напитка, изготавливаемого из кисломолочного напитка ...
Добавлено: 10 июня 2026 г.
Butorova A., Bobakov V., Sergeev A. и др., European Physical Journal: Special Topics 2026 P. 1–19
Добавлено: 10 июня 2026 г.
Добавлено: 19 мая 2026 г.
Добавлено: 28 апреля 2026 г.
Добавлено: 20 апреля 2026 г.
Медведев В. О., / Series arXiv "math". 2026.
We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...
Добавлено: 3 апреля 2026 г.
Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.
Добавлено: 2 апреля 2026 г.
Каймаков К. В., Малышев Д. С., Математические заметки 2025 Т. 117 № 5 С. 672–679
В данной работе рассматривается задача о минимальном остовном дереве (кратко, ЗМОД) на произвольном множестве $n$ точек $d$-мерного пространства в $l_1$-норме. Для этой задачи при каждом фиксированном $d\geq 2$ известен алгоритм сложности $O\big(n\cdot (\log\,n + \log^{r_d}\,n\cdot \log\log\,n)\big)$, где $r_d\in \{0,1,2,4\}$ при $d\in \{2,3,4,5\}$ и $r_d=d$ при $d\geq 6$. Для $d=3$ известно улучшение этого результата до сложности ...
Добавлено: 18 января 2025 г.
Guo Z., Jiang T., Wang G. и др., Journal of Computational and Applied Mathematics 2025 Vol. 463
Добавлено: 16 декабря 2024 г.
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2025 Vol. 19 P. 1441–1454
Добавлено: 5 ноября 2024 г.
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283
Добавлено: 18 апреля 2024 г.
Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801
Добавлено: 16 февраля 2024 г.
The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...
Добавлено: 5 января 2024 г.