A recognition algorithm for the intersection graphs of directed paths in directed trees

Cites Work

Incidence matrices and interval graphs
Title not available (Why is that?)
Transitive Orientation of Graphs and Identification of Permutation Graphs
The intersection graphs of subtrees in trees are exactly the chordal graphs
Representation of a finite graph by a set of intervals on the real line
A Characterization of Comparability Graphs and of Interval Graphs
Triangulated graphs and the elimination process
Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
Matrix characterizations of circular-arc graphs
Intersection representations of graphs by arcs

Cited In (37)

Truly non-trivial graphoidal graphs
On the complexity of recognizing directed path families
Results on vertex-edge and independent vertex-edge domination
Algorithms and complexity of sandwich problems in graphs (extended abstract)
Linear algorithms for chordal graphs of bounded directed vertex leafage
Optimal tree 3-spanners in directed path graphs
Diameter determination on restricted graph families
Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
Intersection graphs of paths in a tree
Center location problems on tree graphs with subtree-shaped customers
Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
Pairwise compatibility graphs: a survey
On the algorithmic complexity of edge total domination
Two new characterizations of path graphs
Burling graphs, chromatic number, and orthogonal tree-decompositions
Intersection graphs of non-crossing paths
Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
Recognizing Helly edge-path-tree graphs and their clique graphs
Finding the minimum bandwidth of an interval graph
The forbidden subgraph characterization of directed vertex graphs
A recognition algorithm for the intersection graphs of paths in trees
Recognition algorithm for intersection graphs of edge disjoint paths in a tree
Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction
On the model-checking of monadic second-order formulas with edge set quantifications
Recognizing clique graphs of directed and rooted path graphs
Directed path graph isomorphism
Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
Classes of intersection digraphs with good algorithmic properties
Computing residual connectedness reliability for restricted networks
Intersection graphs of vertex disjoint paths in a tree
Hamiltonian circuits in interval graph generalizations
Intersection representations of matrices by subtrees and unicycles on graphs
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
The complexity of the locally connected spanning tree problem
A faster algorithm to recognize undirected path graphs
Representations of graphs and networks (coding, layouts and embeddings)

This page was built for publication: A recognition algorithm for the intersection graphs of directed paths in directed trees

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