По отношение на статията

По отношение на статията Embedding Grids into Grids: Dilation Four Suffices, моят принос е минимален. Статията подобрява предишен резултат за grid embedding, а именно „разтеглянето” (dilation) на ребрата; предният резултат беше 6, статията показва, че разтеглянето е не повече от 4. И общата идея, и доказателствата, и типографията на LaTeX са на Джон Елис. Аз дадох някои идеи по детайли на доказателствата и писах софтуер на С като помощ за основния автор.

По отношение на статията In-Situ, Stable Merging by way of the Perfect Shuffle, приносът ми е по-сериозен, макар че основният автор е отново Джон Елис. Основната идея е на Джон Елис: ако се извърши перфектно „разбъркване” (shuffle) на две сортирани редици числа с една и съща големина, вероятно резултатът е доста близо до сортирана последователност. Аз дадох контрапример на Елис (цитиран в статията като най-лош случай), опровергаващ неговата идея за това как редицата да бъде до-сортирана бързо, и при изследването на имплементацията „на място” (in situ, тоест с константна допълнителна памет) разпознах появата на т. нар. necklaces (стрингове-представители на класове на еквивалентност спрямо стрингова ротация).

По отношение на статията Computing the vertex separation of unicyclic graphs, моят принос е основен, макар че идеята да се решава точно тази задача беше на Джон Елис. Предишният най-добър алгоритъм за задачата Vertex Separation върху унициклични графи беше със сложност Ω(n¹¹) (няма печатна грешка, именно Ω, а не O); по-точно, алгоритъмът на Bodlaender и Kloks, работещ в Ω(n^4k+3) върху графи с дървоподобност (treewidth) k. Фолклорът казваше, че групата на известния Langston се е опитала да реши Vertex Separation върху графи със само едно ребро повече от дървета, а именно уницикличните графи, и се е отказала. Разбиването на случаи и подслучаи в нашия алгоритъм, както и ключовото наблюдение за необходимостта от рекурсивно викане в един от подслучаите, са мои. Доказателствата за коректност са почти изцяло мои. Понятието stretching е въведено от мен; преди това имаше extendability на Скодинис, което е частен случай на stretching. Аз видях и доказах факта, че по отношение на дърветата с корен, възможността за extending съществува тогава и само тогава, когато дървото не е критично (понятието „критичност” е въведено в началото на 90те от Джон Елис и други автори и е ключово за линейния алгоритъм за тази задача върху дървета). Джон Елис направи типографското оформяне на LaTeX, както и добави няколко страници свой материал, касаещ оптимални разполагания (linear layouts) на дървета в линейно време.

Статията On the vertex separation of cactus graphs е изцяло моя. Тя разглежда опита да се обобщи подходът от уницикличните графи към кактусови графи (които, в някакъв смисъл, са множество унициклични графи, „слепени” един към друг по дървоподобен начин) и показва ясно провалът на този опит, както и въвежда ключовото понятие stretchability по отношение на множество от двойки върхове. Статията показа, че при решаването на тази задача върху кактуси трябва да започнем със Stretchability като основна задача, а Vertex Separation е неин частен случай.

Статията The reversibility of graph layout multistretchability, изцяло моя, съдържа един важен опорен резултат, а именно, че „разтегливостта” по отношение на множество от двойки върхове е ляво-дясно симетрична, също както основната задача Vertex Separation е ляво-дясно симетрична. Това доказателство опростява много бъдещата работа върху задачата, защото премахва необходимостта да свързаваме едното подмножество върхове именно с лявата посока, а другото, именно с дясната.

Статията On the vertex separation of maximal outerplanar graphs е изцяло моя. Тя съдържа доказателство на необходимо и достатъчно условие, щото vertex separation на максимално външнопланарен граф да е k. За съжаление, тази теорема редуцира задачата до друга задача, за която просто необходимо и достатъчно условие не е намерено. Опити за решаване на Vertex Separation в линейно или квадратично време върху максимално външнопланарни графи е имало в миналото, примерно в личен разговор с Andrzej Proskurowski от университета на Орегон знам, че бившият му студент Ян Арне Теле, в момента известен учен в Норвегия, се е опитвал близо година да открия такъв алгоритъм и се е отказал. Действително, моите опити също не доведоха до успех, но все пак успях да открия и докажа някакво необходимо и достатъчно условие, което може да се окаже полезно за бъдещи опити за откриване на такъв алгоритъм.

В статията Reconstruction of Trees Using Metric Properties моето участие е второстепенно. Задачата е поставена от другите двама автори и алгоритъмът е дело на Красимир Манев. Моят принос е помощ при анализа на сложността по време и свързаното с това въвеждане на понятието „нередуцируемо дърво”, благодарение на което се избягват дълги поредици върхове от степен 2 в дървото при анализа на сложността.

Статията A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs има странна история. Един и същи резултат по почти едно и също време бе постигнат независимо от два екипа, между които нямаше никаква комуникация: Красимир Манев и аз в София, от една страна, и Йонут Мъгурел Андрейка и Николае Цапуш в Букурещ, от друга. Резултатът е линеен алгоритъм за задачата Най-дълъг път , която е NP-пълна върху общи графи, върху кактусови графи. И двата екипа постигнаха линеен алгоритъм, изграден върху схемата Разделяй-и-Владей, като първо кактусът се прави коренов и после се конструират етикети по върховете, отдолу нагоре спрямо вкоренеността. Що се отнася до нашия екип, общата идея беше моя и реализацията, до голяма степен, също. Сравнението между нашата работа и тази на румънския екип показа, че те имат по-проста и елегантна процедура за подзадачата, да се открие в линейно време дължината на най-дълъг път, съдържащ ребро от даден цикъл, ако са известни дължините на най-дълги пътища в подграфите (кактуси), „залепени” към върховете на цикъла, които най-дълги пътища имат за един край съответния връх от цикъла. И така, в отпечатаната версия присъства решението на румънския екип, а не нашето. От друга страна, нашето решение беше несравнимо по-прецизно и подробно написано и типографската работа по оформянето на статията я извърших аз. Предисторията на това изследване също е интересна. Нашето внимание към тази задача бе привлечено от статия на Уехара и Уно, даваща квадратичен алгоритъм за същото нещо (най-дълъг път в кактуси). Ние дадохме линеен алгоритъм, но при опит да публикуваме на същата конференция, на която е бил публикуван резултатът на Уехара и Уно се оказа, че в някакъв чисто теоретичен смисъл, още в края на 80те, холандецът Bodlaender е дал алгоритъм за най-дълъг път върху графи с дървоподобност k, работещ в O(k! 2^k n). За k=const това означава линеен алгоритъм. Вниманелното изследване на този резултат показа, че такъв алгоритъм не е публикуван, а е споменато , че принципно е възможно да бъде конструиран. Но така или иначе това означава, че е невъзможно да се публикува следващ линеен алгоритъм за тази задача върху кактуси (които имат дървоподобност 2) в добро теоретично списания. Как при това е бил публикуван резултатът на Уехара и Уно остана неясно.

Статията A Linear Time Algorithm for Computing Longest Paths in 2-Trees е почти изцяло моя. С Красимир Манев дискутирахме възможността кактусовият резултат да бъде обобщен за, примерно, външнопланарни графи, но идеята да се започне с 2-дървета и да се ползват етикети с константна големина (седем), както и детайлите по изработването на етикети от етикетите на под-2-дърветата, са мои. Споменатото в статията обобщаване на резултата за частични 2-дървета принадлежи на Цветалин Василев, който също така коригира някои мои неточности в доказателствата. В абстрактно-теоретичен смисъл, споменатият горе резултат на Bodlaender обезсмисля усилието, вложено в тази статия. Но в по-практичен план, нашият алгоритъм е прост и елегантен, написан е съвсем подробно (студентка на Цветалин Василев го имплементира и те заедно публикуваха експериментални резултати) и има прецизна верификация, докато алгоритъмът на Bodlaender е по-скоро скициране на идея, почиваща на високо теоретични съображения и едва ли някой някога ще се опита да го програмира.

Статията Algorithmic Results on a Novel Computational Problem е съвместна работа с Красимир Манев. Той предложи задачата а аз предложих алгоритъм, базиран на вкореняване на кактуса. Моят алгоритъм обаче взема за даденост голямо количество информация с обяснението, че същата би могла да се получи лесно след preprocessing на кактуса чрез модифициран DFS. Красимир Манев направи работеща имплементация и откри, че получаването на тази информация съвсем не е толкова тривиално, ако искаме да сложността да бъде линейна. При окончателното писане на статията приносът на Красимир Манев за алгоритъма беше значителен. Доказателството за NP-трудност (NP-hardness) е мое. Доказателството за принадлежност към NP също е мое, но за него значителен принос има Красимир Манев, защото множество съществени детайли се установиха след дълга дискусия с него.

Сборникът със задачи по алгоритми възникна първоначално като място, в което слагах личните си записки, върху които водех упражнения по Дизайн и Анализ на Алгоритми във ФМИ. С времето слагах и все повече теоретични обосновки наред с решените задачи, както и помощни математически резултати в апендикса. Сборникът в сегашната си версия покрива доста добре задачите, които се дават в курса, като обемът му е доста голям – последната версия има 251 страници. Написан е на английски, тъй като това е универсалният език на алгоритмите. Аз не съм мислил за хартиено издание, не съм спечелил нищо материално от този значителен труд и бих искал трудът ми да е достъпен за колкото се може повече хора, тъй като аз самият съм ползвал многократно безплатни и свободни материали (handouts) по Интернет. Сборникът е изцяло мой труд. Имаше грешки, които други хора откриха, и в секцията Acknowledgements съм изказал благодарност на всички, посочили грешки. Но решенията в сборника са мои (освен когато съм ползвал общоизвестни неща или отделни решения на други хора, които са ясно обозначени като такива), написването и изцяло мое, илюстрациите са правени изцяло от мен. Твърдя, че като прецизност, типографско качество и подробност на изложението сборникът е много добър. Всички предложени задачи са с решения – моето мнение е, че ако човек иска да се упражнява, може волево да откаже да гледа решението, поне на първо време, така че е много по-добре задачите да се дават с подробни решения. Ползваната типографска система е LaTeX с множество допълнителни пакети плюс средството за рисуване xfig, което, доколкото ми е известно, е единственото, позволяващо да се разполага върху фигура текст, форматиран от LaTeX по точно същия начин, по който е форматиран целия документ.