Recognition algorithm for intersection graphs of edge disjoint paths in a tree
DOI10.1016/0020-0190(94)90091-4zbMath0790.05084OpenAlexW1975211669MaRDI QIDQ1318763
B. S. Panda, Saraju P. Mohanty
Publication date: 5 April 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)90091-4
treecharacterizationsrecognitionintersection graphsedge-disjoint pathsparallel NC algorithmlinear time sequential algorithm
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- A slice genus lower bound from \(sl(n)\) Khovanov-Rozansky homology
- Edge and vertex intersection of paths in a tree
- Triangulated edge intersection graphs of paths in a tree
- Decomposition by clique separators
- Intersection graphs of paths in a tree
- 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
- A recognition algorithm for the intersection graphs of paths in trees
- Parallel concepts in graph theory
- A characterisation of rigid circuit graphs
- A faster algorithm to recognize undirected path graphs
- Intersection representations of graphs by arcs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- An Efficient Parallel Biconnectivity Algorithm
- Parallel Merge Sort
- A Characterization of Block-Graphs
- Representations of chordal graphs as subtrees of a tree
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
This page was built for publication: Recognition algorithm for intersection graphs of edge disjoint paths in a tree
