On the complexity of recognizing directed path families

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

zbMATH Keywords

recognition algorithms; hypergraph 2-colorability; directed line graph; directed path family

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Related Items

Classification of de Bruijn-based labeled digraphs, Imperfect production process with learning and forgetting effects

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