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

DOI10.1007/S00453-004-1125-YMaRDI QIDQ1774147zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Dimitrios M. Thilikos, Mohammad T. 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

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

Recommendations

• scientific article; zbMATH DE number 1979505
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor

Cited in

(22)

• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Optimization and Recognition for K 5-minor Free Graphs in Linear Time
• Linearity of grid minors in treewidth with applications through bidimensionality
• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Counting problems in parameterized complexity
• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
• \textsc{max-cut} and containment relations in graphs
• Max-Cut and containment relations in graphs
• Subexponential parameterized algorithms
• Confronting intractability via parameters
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Exponential time algorithms for the \textsc{minimum dominating set} problem on some graph classes
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• Quickly deciding minor-closed parameters in general graphs
• scientific article; zbMATH DE number 1979505 (Why is no real title available?)
• Genus characterizes the complexity of certain graph problems: Some tight results
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
• Revising Johnson's table for the 21st century

This page was built for publication: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1774147)