An improved algorithm for the longest induced path problem on k-chordal graphs

DOI10.1016/J.DAM.2008.01.019MaRDI QIDQ1005252zbMATH OpenOpenAlexFDO

Authors Tetsuya Ishizeki, Yota Otachi, Koichi Yamazaki

Publication date 9 March 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.01.019

zbMATH Keywords

\(k\)-chordal graphalgorithmlongest induced path problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Exact and approximate algorithms for the longest induced path problem
• On exact solution approaches for the longest induced path problem
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• scientific article; zbMATH DE number 4117882
• Efficient algorithms for minimal disjoint path problems on chordal graphs
• New formulations and branch-and-cut procedures for the longest induced path problem
• The \(k\)-disjoint paths problem on chordal graphs
• On approximating the longest path in a graph
• On approximating the longest path in a graph
• A linear algorithm for the group path problem on chordal graphs

Cites work

• Algorithms for maximum weight induced paths
• Dually Chordal Graphs
• Estimating all pairs shortest paths in restricted graph families: a unified approach
• Finding large holes
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2159659 (Why is no real title available?)
• On the Number of Minimum Cuts in a Graph
• The approximation of maximum subgraph problems
• Treewidth for graphs with small chordality

Cited in

(10)

• On exact solution approaches for the longest induced path problem
• Mim-width. I. Induced path problems
• An experimental study of ILP formulations for the longest induced path problem
• New formulations and branch-and-cut procedures for the longest induced path problem
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Exact and approximate algorithms for the longest induced path problem
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Vertex sequences in graphs
• MIP formulations for induced graph optimization problems: a tutorial
• Contracting to a longest path in H-free graphs

This page was built for publication: An improved algorithm for the longest induced path problem on \(k\)-chordal graphs

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