On the intractability landscape of digraph intersection representations

DOI10.1007/978-3-031-06678-8_20OpenAlexW4285251856MaRDI QIDQ2169961

Ferdinando Cicalese, Andrea Caucchiolo

Publication date: 30 August 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-06678-8_20

zbMATH Keywords

NP-hardnessintersection numberinapproximabilityarborescencesasymptotic fully polynomial time approximation schemes

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Applications of edge coverings by cliques
• Connection digraphs and second-order line digraphs
• Zero knowledge and the chromatic number
• On the complexity of directed intersection representation of DAGs
• Nearly Tight Approximability Results for Minimum Biclique Cover and Partition
• A digraph represented by a family of boxes or spheres
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Interval digraphs: An analogue of interval graphs
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• The Minimum Satisfiability Problem
• On the hardness of approximating minimization problems
• Directed Intersection Representations and the Information Content of Digraphs
• Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
• The Representation of a Graph by Set Intersections

This page was built for publication: On the intractability landscape of digraph intersection representations