On the complexity of recognizing directed path families
From MaRDI portal
Publication:967290
DOI10.1016/j.dam.2009.03.006zbMath1211.05049MaRDI QIDQ967290
Nicola Apollonio, Paolo Giulio Franciosa
Publication date: 28 April 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.03.006
68Q25: Analysis of algorithms and problem complexity
05C65: Hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The edge intersection graphs of paths in a tree
- Edge and vertex intersection of paths in a tree
- Intersection graphs of paths in a tree
- An efficient PQ-graph algorithm for solving the graph-realization problem
- Hypergraphes de chaînes d'aretes d'un arbre
- A note on line digraphs and the directed max-cut problem
- The underlying graph of a line digraph
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- The matroids with the max-flow min-cut property
- A recognition algorithm for the intersection graphs of paths in trees
- The arborescence-realization problem
- On some properties of DNA graphs
- Incidence matrices and interval graphs
- A characterization of partial directed line graphs
- An Almost Linear-Time Algorithm for Graph Realization
- Graph Classes: A Survey