Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

zbMATH Open1423.05179MaRDI QIDQ4633929FDOQ4633929

Authors: Yusuke Kobayashi, Ken-ichi Kawarabayashi 

Publication date: 6 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=1496894

Recommendations

• Algorithms for finding an induced cycle in planar graphs
• Induced circuits in planar graphs
• Induced packing of odd cycles in planar graphs
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• scientific article; zbMATH DE number 475589

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Cited In (28)

• Few induced disjoint paths for \(H\)-free graphs
• Few induced disjoint paths for \(H\)-free graphs
• Exact Solution Algorithms for the Chordless Cycle Problem
• The disjoint paths problem in quadratic time
• Algorithms for the edge-width of an embedded graph
• MIP formulations for induced graph optimization problems: a tutorial
• A faster algorithm to recognize even-hole-free graphs
• Induced packing of odd cycles in planar graphs
• Title not available (Why is that?)
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• An Improved Algorithm for Finding Cycles Through Elements
• Confronting intractability via parameters
• Induced disjoint paths in claw-free graphs
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Subexponential algorithms for partial cover problems
• Irrelevant vertices for the planar disjoint paths problem
• Combing a Linkage in an Annulus
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Finding and listing induced paths and cycles
• Finding disjoint paths in split graphs
• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Algorithms for finding an induced cycle in planar graphs
• Title not available (Why is that?)
• Computing paths of large rank in planar frameworks deterministically
• Parameterized algorithms for list \(K\)-cycle
• A faster algorithm to recognize even-hole-free graphs

This page was built for publication: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

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