Recognition algorithm for intersection graphs of edge disjoint paths in a tree

DOI10.1016/0020-0190(94)90091-4MaRDI QIDQ1318763zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

characterizationsedge-disjoint pathsintersection graphslinear time sequential algorithmparallel NC algorithmrecognitiontree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Intersection graphs of vertex disjoint paths in a tree
• scientific article; zbMATH DE number 3912430
• scientific article; zbMATH DE number 4116559
• A faster algorithm to recognize undirected path graphs
• scientific article; zbMATH DE number 4049085

Cites work

• A characterisation of rigid circuit graphs
• A Characterization of Block-Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• A faster algorithm to recognize undirected path graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• A slice genus lower bound from \(sl(n)\) Khovanov-Rozansky homology
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Efficient Parallel Biconnectivity Algorithm
• Decomposition by clique separators
• Edge and vertex intersection of paths in a tree
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Intersection graphs of paths in a tree
• Intersection representations of graphs by arcs
• Parallel concepts in graph theory
• Parallel Merge Sort
• Representations of chordal graphs as subtrees of a tree
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Triangulated edge intersection graphs of paths in a tree

Cited in

(6)

• Intersection graphs of vertex disjoint paths in a tree
• A faster algorithm to recognize undirected path graphs
• A linear time and space algorithm for detecting path intersection
• scientific article; zbMATH DE number 3912430 (Why is no real title available?)
• scientific article; zbMATH DE number 4116559 (Why is no real title available?)
• Intersection graphs of non-crossing paths

This page was built for publication: Recognition algorithm for intersection graphs of edge disjoint paths in a tree

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