A faster algorithm to recognize undirected path graphs

DOI10.1016/0166-218X(93)90116-6zbMATH Open0770.68096MaRDI QIDQ2367409FDOQ2367409

Authors: Alejandro A. Schäffer 

Publication date: 10 August 1993

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

Recommendations

• scientific article; zbMATH DE number 3912430
• scientific article; zbMATH DE number 4116559
• Recognition algorithm for intersection graphs of edge disjoint paths in a tree
• Intersection graphs of vertex disjoint paths in a tree

zbMATH Keywords

chordal graphsintersection graphundirected path graphs

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Intersection graphs of paths in a tree
• 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
• A Characterization of Comparability Graphs and of Interval Graphs
• Triangulated graphs and the elimination process
• The maximum k-colorable subgraph problem for chordal graphs
• On the Desirability of Acyclic Database Schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• 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?)
• The NP-completeness column: an ongoing guide
• Degrees of acyclicity for hypergraphs and relational database schemes
• A characterisation of rigid circuit graphs
• Intersection representations of graphs by arcs

Cited In (17)

• Recognizing clique graphs of directed edge path graphs
• Linear algorithms for chordal graphs of bounded directed vertex leafage
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two new characterizations of path graphs
• Extending partial representations of subclasses of chordal graphs
• Recognising the overlap graphs of subtrees of restricted trees is hard
• Intersection graphs of non-crossing paths
• The forbidden subgraph characterization of directed vertex graphs
• Recognition algorithm for intersection graphs of edge disjoint paths in a tree
• Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
• Recognizing vertex intersection graphs of paths on bounded degree trees
• From path graphs to directed path graphs
• The vertex leafage of chordal graphs
• Intersection representations of matrices by subtrees and unicycles on graphs
• Characterizing path graphs by forbidden induced subgraphs
• Faster algorithm to find anti-risk path between two nodes of an undirected graph

This page was built for publication: A faster algorithm to recognize undirected path graphs

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