Algorithms for maximum weight induced paths

DOI10.1016/S0020-0190(01)00222-8zbMath1013.68135OpenAlexW2065908606WikidataQ29013463 ScholiaQ29013463MaRDI QIDQ1603504

Fanica Gavril

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00222-8

zbMATH Keywords

graph algorithmssplit decompositioninterval-filament graphlongest induced path

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (14)

Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ Spanners for bounded tree-length graphs ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Mim-width. I. Induced path problems ⋮ New formulations and branch-and-cut procedures for the longest induced path problem ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ 3D-interval-filament graphs ⋮ Contracting to a longest path in H-free graphs ⋮ On exact solution approaches for the longest induced path problem ⋮ An improved algorithm for the longest induced path problem on \(k\)-chordal graphs ⋮ Unnamed Item

Cites Work

• Maximum weight independent sets and cliques in intersection graphs of filaments
• Trapezoid graphs and generalizations, geometry and algorithms
• Decomposition by clique separators
• Star-cutsets and perfect graphs
• Thresholds for classes of intersection graphs
• Path parity and perfection
• Intersection graphs of Helly families of subtrees
• An O(n2) Algorithm for Undirected Split Decomposition
• Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions
• Unnamed Item

This page was built for publication: Algorithms for maximum weight induced paths