Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors

DOI10.1007/s00453-004-1125-yzbMath1065.68110OpenAlexW2046367433MaRDI QIDQ1774147

Erik D. Demaine, Dimitrios M. Thilikos, Mohammad Taghi Hajiaghayi

Publication date: 29 April 2005

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1125-y

zbMATH Keywords

planar graphsexponential speedup

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms, Genus characterizes the complexity of certain graph problems: Some tight results, Unnamed Item, Unnamed Item, \textsc{max-cut} and containment relations in graphs, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, Subexponential parameterized algorithms, Confronting intractability via parameters, Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes, Linearity of grid minors in treewidth with applications through bidimensionality, Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms, max-cut and Containment Relations in Graphs, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Parameterized complexity of the maximum independent set problem and the speed of hereditary properties, Revising Johnson's table for the 21st century