Tuesday 29 October 2013

Tree inclusion problem

Вступление
В связи с разработкой одной классной штуки приходится читать сложные материалы по теории графов на английском. И некоторые штуки слишком быстро вылетают из головы. И для упорядочивания знаний, я попишу коротко о некоторых терминах из теории графов о которых нет инфы в рунете.

Включенное дерево(Inclusion tree) - это маркированное дерево P, которое можно получить из маркированного дерева T путем удаления его узлов, если узел v дерева T удален, то все ребра идущие из него заменяются на ребра из родителя v к его детям.

Красный узел -- узел который удаляем.

Вроде бы аналогичным понятием является embedded tree.  Применений много не знаю, только вот для запросов в структурированные текстовые базы данных.

Можно почитать:

  1. http://www.cs.ucr.edu/~stelo/cpm/cpm03/Valiente.pdf
  2. http://www.mathnet.ru/links/1140e3926c2d8debfd832352d2bd60df/znsl2144.pdf
  3. http://link.springer.com/chapter/10.1007%2F3-540-57182-5_13#page-1(хотят бабосы)
  4. http://www2.imm.dtu.dk/~inge/treeInclusion.pdf


Alarm!!! Этого поста не должно было быть, я перепутал понятия Tree inclusion problem и Inclusion tree. Хоть понятия и пересекаются, но не совсем о том :) Но не удалять же пост

No comments:

Post a Comment