文章基本信息

标题：Directed Hamiltonicity and Out-Branchings via Generalized Laplacians
本地全文：下载
作者：Andreas Bj{\"o}rklund ; Petteri Kaski ; Ioannis Koutis 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：91:1-91:14
DOI：10.4230/LIPIcs.ICALP.2017.91
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We are motivated by a tantalizing open question in exact algorithms: can we detect whether an n-vertex directed graph G has a Hamiltonian cycle in time significantly less than 2^n? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant 0
关键词：counting; directed Hamiltonicity; graph Laplacian; independent set; k-internal out-branching