Induced disjoint paths and connected subgraphs for \(H\)-free graphs

DOI10.1007/s00453-023-01109-zOpenAlexW4360985664MaRDI QIDQ6053467

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

Publication date: 27 September 2023

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

connectivityinduced subgraphscomplexity dichotomy\(H\)-free graph

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• A new characterization of \(P_k\)-free graphs
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• A new characterization of \(P_{6}\)-free graphs
• Partitioning graphs into connected parts
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• On the complexity of testing for odd holes and induced odd paths
• Two-segmented channel routing is strong NP-complete
• Graph minors. XIII: The disjoint paths problem
• Induced disjoint paths in AT-free graphs
• Few induced disjoint paths for \(H\)-free graphs
• Mim-width. I. Induced path problems
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Detecting fixed patterns in chordal graphs in polynomial time
• The \(k\)-in-a-path problem for claw-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Induced disjoint paths in circular-arc graphs in linear time
• Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Induced Disjoint Paths in Claw-Free Graphs
• The complexity of satisfiability problems
• Detecting induced subgraphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Contracting to a longest path in H-free graphs
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time

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