• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 17 публикаций
Сортировка:
по названию
по году
Статья
Beaudou L., Nourine L., Mary A. Theoretical Computer Science. 2017. Vol. 658. P. 391-398.
Добавлено: 11 апреля 2019
Статья
Belova T., Bliznets I. Theoretical Computer Science. 2020. No. 803. P. 222-233.
Добавлено: 6 февраля 2020
Статья
Durand B., Gamard G., Grandjean A. Theoretical Computer Science. 2017. Vol. 666. P. 36-47.
Добавлено: 10 октября 2017
Статья
Shitov Y. Theoretical Computer Science. 2017. Vol. 671. P. 116-118.
Добавлено: 15 марта 2017
Статья
Korpelainen N., Lozin V. V., Malyshev D. et al. Theoretical Computer Science. 2011. No. 412. P. 3545-3554.

Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. В частности, мы выявляем два граничных класса для задачи о гамильтоновом цикле и доказываем, что при k>3 существует континуум граничных классов для задачи о вершинной k-раскраске.

Добавлено: 11 сентября 2012
Статья
Maxim Babenko, Gawrychowski P., Kociumaka T. et al. Theoretical Computer Science. 2016. Vol. 638. P. 112-121.

We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length . n. For the minimal suffix problem we show that for every . τ, . 1≤τ≤logn, there exists a linear-space data structure with . O(τ) query time and . O(nlogn/τ) preprocessing time. As a sample application, we show that this data structure can be used to compute the Lyndon decomposition of any substring of the text in . O(kτ) time, where . k is the number of distinct factors in the decomposition. For the maximal suffix problem, we give a linear-space structure with . O(1) query time and . O(n) preprocessing time. In other words, we simultaneously achieve both the optimal query time and the optimal construction time. © 2015 Elsevier B.V.

Добавлено: 8 октября 2015
Статья
Vereshchagin N. Theoretical Computer Science. 2020. Vol. 809. P. 531-537.
Добавлено: 17 января 2020
Статья
Babin M. A., Kuznetsov S. Theoretical Computer Science. 2017. Vol. Volume 658, Part B. No. 7 January. P. 316-326.

Dualization of a monotone Boolean function on a finite lattice can be represented by transforming the set of its minimal 1 values to the set of its maximal 0 values. In this paper we consider finite lattices given by ordered sets of their meet and join irreducibles (i.e., as a concept lattice of a formal context). We show that in this case dualization is equivalent to the enumeration of so-called minimal hypotheses. In contrast to usual dualization setting, where a lattice is given by the ordered set of its elements, dualization in this case is shown to be impossible in output polynomial time unless P = NP. However, if the lattice is distributive, dualization is shown to be possible in subexponential time.

Добавлено: 9 февраля 2017
Статья
Slavnov S. A. Theoretical Computer Science. 2006. Vol. 357. No. 1-3. P. 215-229.
Добавлено: 4 марта 2013
Статья
Zhivotovskiy N., Hanneke S. Theoretical Computer Science. 2018. Vol. 9. No. 742. P. 27-49.
Добавлено: 6 декабря 2018
Статья
Bliznets I., Sagunov D. Theoretical Computer Science. 2020. Vol. 838. P. 94-110.
Добавлено: 8 октября 2020
Статья
Lozin V. V., Malyshev D., Mosca R. et al. Theoretical Computer Science. 2017. Vol. 700. P. 63-74.
Добавлено: 28 августа 2017
Статья
Beaudou L., Coupechoux P., Dailly A. et al. Theoretical Computer Science. 2018. Vol. 746. P. 19-35.
Добавлено: 11 апреля 2019
Статья
Shitov Y. Theoretical Computer Science. 2017. Vol. 660. P. 102-104.
Добавлено: 19 декабря 2016
Статья
Obiedkov S. Theoretical Computer Science. 2017. Vol. 658. No. Part B. P. 375-390.
Добавлено: 2 апреля 2016
Статья
Fana N., Zhengb Q. P., Pardalos P. M. Theoretical Computer Science. 2012. Vol. 447. P. 53-61.

Задача разбиения графа заключается в разделении множества вершин графа на число непустых подмножеств так, чтобы общий вес ребер,  соединяющих различные подмножества сводился  к минимуму. Предшествующие исследования требуют ввода мощностей подмножеств или числа подмножеств  для равнораспределения. В этой статье, проблема формулируется как  Zero-one задача квадратичного программирования без ввода мощностей. Мы также представляем три формулировки  равнозначного Zero-one линейного целого программирования. Из-за его важности в bi – кластеризации  данных,  разбиение двудольных графов также изучается. Для практического применения также описываются несколько новых методов определения  числа подмножеств и мощности. Кроме того, изучается  иерархия разделения и разбиения двудольных графов без переназначения одного множества вершин.

Добавлено: 31 декабря 2012
Статья
Boros E., Gurvich V., Bao Ho N. et al. Theoretical Computer Science. 2019. Vol. 799. P. 40-58.
Добавлено: 9 декабря 2019