Planar Subgraph Isomorphism Revisited
From MaRDI portal
Publication:3113755
DOI10.4230/LIPIcs.STACS.2010.2460zbMath1230.68230MaRDI QIDQ3113755
Publication date: 23 January 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_7d84.html
dynamic programming; graph algorithms; NP-hard problems; subgraph isomorphism; topological graph theory
68W40: Analysis of algorithms
90C39: Dynamic programming
05C10: Planar graphs; geometric and topological aspects of graph theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, A Linear-Time Parameterized Algorithm for Node Unique Label Cover, Slightly Superexponential Parameterized Problems, Subgraph isomorphism on graph classes that exclude a substructure, Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, Quasipolynomiality of the Smallest Missing Induced Subgraph, Polynomial algorithms for open plane graph and subgraph isomorphisms, Subgraph isomorphism in graph classes, Faster parameterized algorithms for minor containment, Linear kernels and linear-time algorithms for finding large cuts, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs, On the complexity of submap isomorphism and maximum common submap problems, Fast minor testing in planar graphs, Polynomial bounds for centered colorings on proper minor-closed graph classes, A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families, A general purpose algorithm for counting simple cycles and simple paths of any length, On approximating the \(d\)-girth of a graph, Computing the Overlaps of Two Maps, What’s Next? Future Directions in Parameterized Complexity, On Approximating the d-Girth of a Graph, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
