On the complexity of recognizing directed path families

DOI10.1016/j.dam.2009.03.006zbMath1211.05049OpenAlexW2067974691MaRDI 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 algorithmshypergraph 2-colorabilitydirected line graphdirected path family

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

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

This page was built for publication: On the complexity of recognizing directed path families