Induced disjoint paths in AT-free graphs

DOI10.1016/j.jcss.2021.10.003zbMath1478.68240arXiv2012.09814OpenAlexW3209626956MaRDI QIDQ2051862

Daniël Paulusma, Erik Jan van Leeuwen, Petr A. Golovach

Publication date: 25 November 2021

Published in: Journal of Computer and System Sciences, Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.09814

zbMATH Keywords

polynomial-time algorithmdisjoint pathsW[1-hardness]AT-free graph\(k\)-in-a-tree\(k\)-in-a-pathco-bipartite graphinduced topological minor

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (14)

Induced disjoint paths in circular-arc graphs in linear time ⋮ Graph editing to a fixed target ⋮ Mim-width. I. Induced path problems ⋮ Detecting induced minors in AT-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Unnamed Item ⋮ Induced disjoint paths in AT-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• On graphs with no induced subdivision of \(K_4\)
• Finding disjoint paths in split graphs
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The three-in-a-tree problem
• The four-in-a-tree problem in triangle-free graphs
• Finding induced trees
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Induced matchings
• Induced circuits in planar graphs
• Graph minors. XIII: The disjoint paths problem
• 3-colouring AT-free graphs in polynomial time
• Domination and total domination on asteroidal triple-free graphs
• Induced disjoint paths in AT-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
• Induced disjoint paths in circular-arc graphs in linear time
• FPT and kernelization algorithms for the induced tree problem
• Colouring AT-Free Graphs
• Representation of a finite graph by a set of intervals on the real line
• Representations of chordal graphs as subtrees of a tree
• On the Computational Complexity of Combinatorial Problems
• Independent Sets in Asteroidal Triple-Free Graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Asteroidal Triple-Free Graphs
• Detecting an induced subdivision of K₄
• Three-in-a-tree in near linear time
• Induced Disjoint Paths in Claw-Free Graphs
• Finding topological subgraphs is fixed-parameter tractable
• Detecting induced subgraphs
• Graph-Theoretic Concepts in Computer Science
• On the structure of graphs with bounded asteroidal number

This page was built for publication: Induced disjoint paths in AT-free graphs