Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions

DOI10.1006/jagm.1994.1031zbMath0807.05035OpenAlexW2091696149MaRDI QIDQ4312221

Dominique de Werra, Fanica Gavril, Valerio Toledano Laredo

Publication date: 30 November 1994

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1031

zbMATH Keywords

holesdirected graphkernelpolynomial time algorithms\(m\)-obstructionchordless directed pathfraternally oriented graphperfectly oriented graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ A characterization of normal fraternally orientable perfect graphs ⋮ A polynomial algorithm for the parity path problem on perfectly orientable graphs ⋮ Perfect graphs, kernels, and cores of cooperative games ⋮ Algorithms for maximum weight induced paths

This page was built for publication: Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions