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

DOI10.1016/0012-365X(75)90021-7zbMath0312.05108OpenAlexW1993412054WikidataQ127740725 ScholiaQ127740725MaRDI QIDQ1219893

Fanica Gavril

Publication date: 1975

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(75)90021-7

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Algorithms in computer science (68W99)

Related Items

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

Cites Work

• Unnamed Item
• Incidence matrices and interval graphs
• Intersection representations of graphs by arcs
• Triangulated graphs and the elimination process
• Matrix characterizations of circular-arc 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
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Characterization of Comparability Graphs and of Interval Graphs