Induced disjoint paths in circular-arc graphs in linear time

DOI10.1016/j.tcs.2016.06.003zbMath1345.05051arXiv1403.0789OpenAlexW1582736073MaRDI QIDQ2629233

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

Publication date: 5 July 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

circular-arc graphslinear-time algorithminduced disjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Mim-width. I. Induced path problems, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, The (theta, wheel)-free graphs. IV: Induced paths and cycles, Few induced disjoint paths for \(H\)-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
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• A simpler linear-time recognition of circular-arc graphs
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear-time recognition of circular-arc graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Graph minors. XIII: The disjoint paths problem
• Induced disjoint paths in AT-free graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• The \(k\)-in-a-path problem for claw-free graphs
• Vertex disjoint paths on clique-width bounded graphs
• Induced Disjoint Paths in Claw-Free Graphs
• Finding Disjoint Paths in Split Graphs
• Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• On the Computational Complexity of Combinatorial Problems
• Large induced subgraphs via triangulations and CMSO