On the complexity of directed intersection representation of DAGs
type: Item
instance of: scholarly article
title: On the complexity of directed intersection representation of DAGs
DOI: 10.1007/978-3-030-58150-3_45
author: Andrea Caucchiolo
author: Ferdinando Cicalese
publication date: 2021-04-21T00:00:00Z
Mathematics Subject Classification ID: 68Rxx
zbMATH DE Number: 7336134
zbMATH Keywords: intersection number
zbMATH Keywords: digraphs
zbMATH Keywords: NP-hardness
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: 978-3-030-58150-3 45
OpenAlex ID: W3082959211
cites work: Connection digraphs and second-order line digraphs
cites work: Interval digraphs: An analogue of interval graphs
cites work: The Representation of a Graph by Set Intersections
cites work: Data reduction and exact algorithms for clique cover
cites work: Covering edges by cliques with regard to keyword conflicts and intersection graphs
cites work: On the hardness of approximating minimization problems
cites work: A digraph represented by a family of boxes or spheres
cites work: Q4152571
Recommended article: Q2766669
Recommended article: On the intractability landscape of digraph intersection representations
Recommended article: Directed Intersection Representations and the Information Content of Digraphs
Recommended article: DAGmaps and ε-Visibility Representations for DAGs: Algorithms and Characterizations
Recommended article: Algorithmic aspects of intersection graphs and representation hypergraphs
Recommended article: Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs
Recommended article: The dag-width of directed graphs
Recommended article: DAGmaps and ε-Visibility Representations of DAGs
Recommended article: Dynamic Complexity of Directed Reachability and Other Problems
Recommended article: On the complexity of recognizing directed path families
description: scientific article; zbMATH DE number 7336134