On the complexity of recognizing directed path families

DOI10.1016/J.DAM.2009.03.006MaRDI QIDQ967290zbMATH OpenOpenAlexFDO

Authors Nicola Apollonio, Paolo G. 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

directed line graphdirected path familyhypergraph 2-colorabilityrecognition algorithms

Mathematics Subject Classification ID

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

Recommendations

• Packing paths in digraphs
• A note on the Hamiltonian circuit problem on directed path graphs
• On the computational complexity of path cover problems
• Complexity of Recognizing Equal Unions in Families of Sets
• NP-completeness of some edge-disjoint paths problems

Cites work

• A characterization of partial directed line graphs
• A note on line digraphs and the directed max-cut problem
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• An Almost Linear-Time Algorithm for Graph Realization
• An efficient PQ-graph algorithm for solving the graph-realization problem
• Edge and vertex intersection of paths in a tree
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3853102 (Why is no real title available?)
• scientific article; zbMATH DE number 4010523 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 863476 (Why is no real title available?)
• scientific article; zbMATH DE number 863480 (Why is no real title available?)
• scientific article; zbMATH DE number 3286813 (Why is no real title available?)
• Hypergraphes de chaînes d'aretes d'un arbre
• Incidence matrices and interval graphs
• Intersection graphs of paths in a tree
• On some properties of DNA graphs
• The arborescence-realization problem
• The edge intersection graphs of paths in a tree
• The matroids with the max-flow min-cut property
• The underlying graph of a line digraph

Cited in

(3)

• Classification of de Bruijn-based labeled digraphs
• On the complexity of directed intersection representation of DAGs
• Imperfect production process with learning and forgetting effects

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q967290)