Intersection graphs of paths in a tree
From MaRDI portal
Publication:1077439
DOI10.1016/0095-8956(86)90042-0zbMATH Open0595.05062OpenAlexW1976489861MaRDI QIDQ1077439FDOQ1077439
Authors: Clyde l. Monma, Victor K. Wei 
Publication date: 1986
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(86)90042-0
Permutations, words, matrices (05A05) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph theory (05C99)
Cites Work
- Title not available (Why is that?)
- Edge and vertex intersection of paths in a tree
- Triangulated edge intersection graphs of paths in a tree
- Decomposition by clique separators
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- A New Algorithm for Generating All the Maximal Independent Sets
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- A Characterization of Comparability Graphs and of Interval Graphs
- Title not available (Why is that?)
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- A recognition algorithm for the intersection graphs of paths in trees
- Title not available (Why is that?)
- A slice genus lower bound from \(sl(n)\) Khovanov-Rozansky homology
- Matrix characterizations of circular-arc graphs
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- A characterisation of rigid circuit graphs
- Title not available (Why is that?)
- An algorithm for finding clique cut-sets
- Line perfect graphs
- An efficient PQ-graph algorithm for solving the graph-realization problem
- Incidence matrices with the consecutive 1’s property
- Intersection representations of graphs by arcs
- Title not available (Why is that?)
- An algorithm for constructing edge-trees from hypergraphs
Cited In (72)
- Characterization of 2-path signed network
- Truly non-trivial graphoidal graphs
- On asteroidal sets in chordal graphs
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Exactly hittable interval graphs
- Two new characterizations of path graphs
- Succinct data structure for path graphs
- Recognising the overlap graphs of subtrees of restricted trees is hard
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Perfect graphs with polynomially computable kernels
- Helly EPT graphs on bounded degree trees: characterization and recognition
- Path Problems in Complex Networks
- Directed acyclic graphs with the unique dipath property
- Path Partitions, Cycle Covers and Integer Decomposition
- Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
- A characterization of substar graphs
- Strong cliques and equistability of EPT graphs
- Recognizing clique graphs of directed edge path graphs
- On the complexity of recognizing directed path families
- End simplicial vertices in path graphs
- Title not available (Why is that?)
- A superclass of edge-path-tree graphs with few cliques
- On spectrum assignment in elastic optical tree-networks
- Coloring all directed paths in a symmetric tree, with an application to optical networks
- Représentations en arbre de proximités relatives
- A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs
- On models of directed path graphs non rooted directed path graphs
- Intersection graphs of concatenable subtrees of graphs
- On basic chordal graphs and some of its subclasses
- Subpath acyclic digraphs
- Title not available (Why is that?)
- Equivalences and the complete hierarchy of intersection graphs of paths in a tree
- Asteroidal quadruples in non rooted path graphs
- Clique graphs and Helly graphs
- The clique-separator graph for chordal graphs
- Decomposition by maxclique separators
- Intersection graphs of non-crossing paths
- Intersection graphs of non-crossing paths
- Clique-coloring UE and UEH graphs
- Recognizing Helly edge-path-tree graphs and their clique graphs
- The forbidden subgraph characterization of directed vertex graphs
- 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
- Recognizing clique graphs of directed and rooted path graphs
- Modular intersection graphs
- Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
- Directed path graph isomorphism
- Recognizing vertex intersection graphs of paths on bounded degree trees
- From path graphs to directed path graphs
- Counting independent sets in a tolerance graph
- An algorithm for fraternal orientation of graphs
- Characterizing width two for variants of treewidth
- Intersection graphs of Helly families of subtrees
- On the correspondence between tree representations of chordal and dually chordal graphs
- Intersection graphs of vertex disjoint paths in a tree
- The separator theorem for rooted directed vertex graphs
- Algorithmic aspects of intersection graphs and representation hypergraphs
- The vertex leafage of chordal graphs
- A note on the Hamiltonian circuit problem on directed path graphs
- Constant tolerance intersection graphs of subtrees of a tree
- Counting clique trees and computing perfect elimination schemes in parallel
- Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
- Total coloring of rooted path graphs
- Characterizing directed path graphs by forbidden asteroids
- Counting maximal independent sets in directed path graphs
- Computing the \(K\)-terminal reliability of directed path graphs
- Revising Johnson's table for the 21st century
- Completeness for intersection classes
- A faster algorithm to recognize undirected path graphs
- Representations of graphs and networks (coding, layouts and embeddings)
This page was built for publication: Intersection graphs of paths in a tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1077439)
