On the complexity of directed intersection representation of DAGs

DOI10.1007/978-3-030-58150-3_45OpenAlexW3082959211MaRDI QIDQ2019504

Ferdinando Cicalese, Andrea Caucchiolo

Publication date: 21 April 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-58150-3_45

zbMATH Keywords

digraphsapproximation algorithmsNP-hardnessintersection number

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

On the intractability landscape of digraph intersection representations

Cites Work

• Unnamed Item
• Connection digraphs and second-order line digraphs
• A digraph represented by a family of boxes or spheres
• Interval digraphs: An analogue of interval graphs
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• On the hardness of approximating minimization problems
• Data reduction and exact algorithms for clique cover
• The Representation of a Graph by Set Intersections

This page was built for publication: On the complexity of directed intersection representation of DAGs