Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials

DOI10.1016/j.jcss.2018.01.004zbMath1391.68055arXiv1706.03698MaRDI QIDQ1747489

Gregory Gutin, Meirav Zehavi, Magnus Wahlström, Felix Reidl

Publication date: 8 May 2018

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.03698

zbMATH Keywords

deterministic; Pfaffians; polynomial space; fixed-parameter tractable; Kirchoff matrices

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C31: Graph polynomials

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)