Hardness and algorithms for variants of line graphs of directed graphs

DOI10.1007/978-3-642-45030-3_19zbMATH Open1329.05275OpenAlexW56220973MaRDI QIDQ2872084FDOQ2872084

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

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

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

Mathematics Subject Classification ID

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

Cited In (4)

• On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs
• A note on line digraphs and the directed max-cut problem
• Bounds on directed star arboricity in some digraph classes
• 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)