Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus

DOI10.1007/11785293_18zbMath1141.05338OpenAlexW2166658560WikidataQ60488761 ScholiaQ60488761MaRDI QIDQ5757875

Frederic Dorn, Dimitrios M. Thilikos, Fedor V. Fomin

Publication date: 7 September 2007

Published in: Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11785293_18

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Contraction bidimensionality of geometric intersection graphs ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Unnamed Item ⋮ How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms ⋮ Approximation algorithms via contraction decomposition ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions ⋮ Subexponential parameterized algorithms ⋮ Faster parameterized algorithms for minor containment ⋮ Confronting intractability via parameters ⋮ Dynamic programming and planarity: improved tree-decomposition based algorithms ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Dynamic programming for graphs on surfaces

This page was built for publication: Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus