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

DOI10.1007/S00453-004-1125-YzbMATH Open1065.68110OpenAlexW2046367433MaRDI QIDQ1774147FDOQ1774147

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

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

zbMATH Keywords

planar graphsexponential speedup

Mathematics Subject Classification ID

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

Cited In (22)

• Coverability and sub-exponential parameterized algorithms in planar graphs
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• 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
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• 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
• Title not available (Why is that?)
• Quickly deciding minor-closed parameters in general graphs
• 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)