Hardness and algorithms for variants of line graphs of directed graphs

DOI10.1007/978-3-642-45030-3_19MaRDI QIDQ2872084zbMATH OpenOpenAlexFDO

Authors Mourad Baïou, Laurent Beaudou, Zhentao Li, Vincent Limouzy

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_19

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 3912430
• On a connection between facility location and perfect graphs
• A characterization of partial directed line graphs
• On the hardness of recognizing triangular line graphs
• The recognition of triangle graphs

Cited in

(5)

• A note on line digraphs and the directed max-cut problem
• On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs
• Bounds on directed star arboricity in some digraph classes
• On the hardness of recognizing triangular line graphs
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: Hardness and algorithms for variants of line graphs of directed graphs

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