文章基本信息

标题：Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk)
本地全文：下载
作者：Thore Husfeldt
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：161
页码：1:1-1:1
DOI：10.4230/LIPIcs.CPM.2020.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：I will give a gentle introduction to algebraic graph algorithms by showing how to determine if a given graph contains a simple path of length k. This is a famous problem admitting a beautiful and widely-known algorithm, namely the colour-coding method of Alon, Yuster and Zwick (1995). Starting from this entirely combinatorial approach, I will carefully develop an algebraic perspective on the same problem. First, I will explain how the colour-coding algorithm can be understood as the evaluation of a well-known expression (sometimes called the "walk-sum" of the graph) in a commutative algebra called the zeon algebra. From there, I will introduce the exterior algebra and present the algebraic framework recently developed with Brand and Dell (2018). The presentation is aimed at a combinatorially-minded audience largely innocent of abstract algebra.
关键词：paths; exterior algebra; wedge product; color-coding; parameterized complexity