RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. Ин-та матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. Ин-та матем., 2010, том 18, номер 2, страницы 55–59 (Mi timb17)  

Хеллиева размерность реберных графов $k$-униформных гиперграфов

Е. В. Крылов

Белорусский государственный университет

Аннотация: Исследуется взаимосвязь хеллиевой и краусовой размерностей (соответственно графов $r$-мино и реберных графов $k$-униформных гиперграфов). Показано, что пересечение классов $r$-мино и реберных графов $k$-униформных гиперграфов не пусто для любых $r\ge k\ge2$. Доказано, что хеллиева размерность может быть вычислена за полиномиальное время от максимальной степени вершин и краусовой размерности графа. Приведены оценки на хеллиеву размерность в терминах краусовой размерности и максимальной степени вершин в графе. Доказано, что задача распознавания “$kd_s(G)\le 3$” является $NP$-трудной в классе $3$-мино.

Полный текст: PDF файл (251 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.1
Поступила в редакцию: 30.12.2009

Образец цитирования: Е. В. Крылов, “Хеллиева размерность реберных графов $k$-униформных гиперграфов”, Тр. Ин-та матем., 18:2 (2010), 55–59

Цитирование в формате AMSBIB
\RBibitem{Kry10}
\by Е.~В.~Крылов
\paper Хеллиева размерность реберных графов $k$-униформных гиперграфов
\jour Тр. Ин-та матем.
\yr 2010
\vol 18
\issue 2
\pages 55--59
\mathnet{http://mi.mathnet.ru/timb17}
\zmath{https://zbmath.org/?q=an:05863490}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timb17
  • http://mi.mathnet.ru/rus/timb/v18/i2/p55

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды Института математики
    Просмотров:
    Эта страница:124
    Полный текст:124
    Литература:17
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020