Induced disjoint paths and connected subgraphs for H-free graphs

DOI10.1007/S00453-023-01109-ZMaRDI QIDQ6053467zbMATH OpenOpenAlexFDO

Authors Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Publication date 27 September 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-023-01109-z

zbMATH Keywords

\(H\)-free graphcomplexity dichotomyconnectivityinduced subgraphs

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• Induced disjoint paths and connected subgraphs for H-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Few induced disjoint paths for \(H\)-free graphs
• Few induced disjoint paths for \(H\)-free graphs
• Induced disjoint paths in claw-free graphs
• Induced disjoint paths in claw-free graphs
• scientific article; zbMATH DE number 4089593

Cites work

• A linear time algorithm for the induced disjoint paths problem in planar graphs
• A new characterization of P_k-free graphs
• A new characterization of \(P_{6}\)-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Contracting to a longest path in H-free graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• Few induced disjoint paths for \(H\)-free graphs
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 4133491 (Why is no real title available?)
• Induced disjoint paths and connected subgraphs for H-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Induced disjoint paths in claw-free graphs
• Mim-width. I. Induced path problems
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On maximal independent sets of vertices in claw-free graphs
• On the complexity of testing for odd holes and induced odd paths
• Partitioning graphs into connected parts
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• The \(k\)-in-a-path problem for claw-free graphs
• The complexity of satisfiability problems
• Two-segmented channel routing is strong NP-complete

Cited in

(1)

• Few induced disjoint paths for \(H\)-free graphs

This page was built for publication: Induced disjoint paths and connected subgraphs for \(H\)-free graphs

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