Dynamic programming for graphs on surfaces
From MaRDI portal
Publication:5501962
DOI10.1145/2556952zbMath1321.05276OpenAlexW1826939887MaRDI QIDQ5501962
Juanjo Rué, Dimitrios M. Thilikos, Ignasi Sau
Publication date: 14 August 2015
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083690/file/dprog.pdf
dynamic programminganalysis of algorithmsnoncrossing partitionsparameterized algorithmsgraphs on surfacesbranchwidthpolyhedral embeddings
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Contraction bidimensionality of geometric intersection graphs ⋮ A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ C-planarity testing of embedded clustered graphs with bounded dual carving-width ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Matching is as easy as matrix inversion
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Graph minors. XVI: Excluding a non-planar graph
- Which problems have strongly exponential complexity?
- On the existence of subexponential parameterized algorithms
- Graph minors. XII: Distance on a surface
- Asymptotic enumeration of non-crossing partitions on surfaces
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Dynamic Programming for H-minor-free Graphs
- The graph genus problem is NP-complete
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- The Bidimensional Theory of Bounded-Genus Graphs
- On self duality of pathwidth in polyhedral graph embeddings
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- Faster Parameterized Algorithms for Minor Containment
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Computing Vertex Connectivity: New Bounds from Old Techniques
- Subexponential Parameterized Algorithms
- Automata, Languages and Programming
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
