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

DOI10.1016/j.dam.2008.01.019zbMath1186.05114OpenAlexW2071594117MaRDI QIDQ1005252

Yota Otachi, Koichi Yamazaki, Tetsuya Ishizeki

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

algorithm\(k\)-chordal graphlongest induced path problem

Mathematics Subject Classification ID

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

Related Items (8)

Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ Mim-width. I. Induced path problems ⋮ New formulations and branch-and-cut procedures for the longest induced path problem ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Contracting to a longest path in H-free graphs ⋮ On exact solution approaches for the longest induced path problem ⋮ Unnamed Item ⋮ Vertex sequences in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding large holes
• Treewidth for graphs with small chordality
• Algorithms for maximum weight induced paths
• Dually Chordal Graphs
• Graph Classes: A Survey
• The approximation of maximum subgraph problems
• On the Number of Minimum Cuts in a Graph
• Estimating all pairs shortest paths in restricted graph families: a unified approach
• Graph-Theoretic Concepts in Computer Science

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