Induced disjoint paths in circular-arc graphs in linear time

DOI10.1016/J.TCS.2016.06.003MaRDI QIDQ2629233zbMATH OpenOpenAlexFDO

Authors Daniël Paulusma, Erik Jan van Leeuwen, 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 graphsinduced disjoint pathslinear-time algorithm

Mathematics Subject Classification ID

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

Abstract: The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,...,k, and P_i and P_j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1<=i < j<=k. We present a linear-time algorithm for Induced Disjoint Paths on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs (s_i,t_i) are not necessarily distinct.

Recommendations

• Induced disjoint paths in circular-arc graphs in linear time
• The Induced Disjoint Paths Problem
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Induced disjoint paths problem in a planar digraph
• Paths in interval graphs and circular arc graphs

Cites work

• A linear time algorithm for the induced disjoint paths problem in planar graphs
• A simpler linear-time recognition of circular-arc graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Detecting fixed patterns in chordal graphs in polynomial time
• Finding disjoint paths in split graphs
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 4133491 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Induced disjoint paths in circular-arc graphs in linear time
• Induced disjoint paths in claw-free graphs
• Large induced subgraphs via triangulations and CMSO
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear-time recognition of circular-arc graphs
• On the Computational Complexity of Combinatorial Problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The \(k\)-in-a-path problem for claw-free graphs
• Vertex disjoint paths on clique-width bounded graphs

Cited in

(10)

• Few induced disjoint paths for \(H\)-free graphs
• Mim-width. I. Induced path problems
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Induced disjoint paths in circular-arc graphs in linear time
• scientific article; zbMATH DE number 140475 (Why is no real title available?)
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Induced disjoint paths and connected subgraphs for H-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Few induced disjoint paths for \(H\)-free graphs

This page was built for publication: Induced disjoint paths in circular-arc graphs in linear time

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