A recognition algorithm for the intersection graphs of paths in trees
From MaRDI portal
Publication:1254334
DOI10.1016/0012-365X(78)90003-1zbMath0398.05060OpenAlexW2036751548MaRDI QIDQ1254334
Publication date: 1978
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(78)90003-1
Trees (05C05) Paths and cycles (05C38) Graph theory (05C99) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
On the Algorithmic Complexity of Total Domination, NeST graphs, Intersection graphs of paths in a tree, Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid, A faster algorithm to recognize undirected path graphs, The recognition of geodetically connected graphs, Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2, Hamiltonian circuits in interval graph generalizations, Characterizing directed path graphs by forbidden asteroids, What Is between Chordal and Weakly Chordal Graphs?, Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I, Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage, Intersection graphs of vertex disjoint paths in a tree, Characterizing width two for variants of treewidth, Max point-tolerance graphs, Algorithmic aspects of intersection graphs and representation hypergraphs, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Subpath acyclic digraphs, Exact square coloring of certain classes of graphs: complexity and algorithms, String graphs. I: The number of critical nonstring graphs is infinite, Intersection graphs of orthodox paths in trees, Constant threshold intersection graphs of orthodox paths in trees, Truly non-trivial graphoidal graphs, On the algorithmic complexity of \(k\)-tuple total domination, A characterization of substar graphs, Two new characterizations of path graphs, A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs, Algorithms and complexity of sandwich problems in graphs (extended abstract), A Refined Analysis of Online Path Coloring in Trees, Total coloring of rooted path graphs, The vertex leafage of chordal graphs, Computing a minimum outer-connected dominating set for the class of chordal graphs, A linear time algorithm for liar's domination problem in proper interval graphs, Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs, Intersection representations of matrices by subtrees and unicycles on graphs, The \(k\)-edge intersection graphs of paths in a tree, Subtree and substar intersection numbers, Representing edge intersection graphs of paths on degree 4 trees, Complexity of distance paired-domination problem in graphs, Towards a comprehensive theory of conflict-tolerance graphs, On the complexity of recognizing directed path families, Intersection graphs of non-crossing paths, Recognizing Helly edge-path-tree graphs and their clique graphs, From Path Graphs to Directed Path Graphs, Equivalences and the complete hierarchy of intersection graphs of paths in a tree, Center location problems on tree graphs with subtree-shaped customers, Recognizing vertex intersection graphs of paths on bounded degree trees, Optimal tree 3-spanners in directed path graphs, Characterizing path graphs by forbidden induced subgraphs, The forbidden subgraph characterization of directed vertex graphs, Revising Johnson's table for the 21st century, The edge intersection graphs of paths in a tree, An algorithm for constructing edge-trees from hypergraphs, Chronological orderings of interval graphs, Edge and vertex intersection of paths in a tree, Triangulated edge intersection graphs of paths in a tree, Extending partial representations of subclasses of chordal 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
- Unnamed Item
- Unnamed Item
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Incidence matrices and interval graphs
- Intersection representations of graphs by arcs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- 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
