A faster algorithm to recognize undirected path graphs

DOI10.1016/0166-218X(93)90116-6MaRDI QIDQ2367409zbMATH OpenFDO

Authors Alejandro A. Schäffer

Publication date 10 August 1993

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

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)

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

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• A characterisation of rigid circuit 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
• 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
• Degrees of acyclicity for hypergraphs and relational database schemes
• Intersection graphs of paths in a tree
• Intersection representations of graphs by arcs
• 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
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The NP-completeness column: an ongoing guide
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Triangulated graphs and the elimination process

Cited in

(17)

• Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
• The forbidden subgraph characterization of directed vertex graphs
• Faster algorithm to find anti-risk path between two nodes of an undirected graph
• Recognizing clique graphs of directed edge path graphs
• 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
• Recognition algorithm for intersection graphs of edge disjoint paths in a tree
• Linear algorithms for chordal graphs of bounded directed vertex leafage
• The vertex leafage of chordal graphs
• Characterizing path graphs by forbidden induced subgraphs
• Extending partial representations of subclasses of chordal graphs
• Intersection representations of matrices by subtrees and unicycles on graphs
• Recognising the overlap graphs of subtrees of restricted trees is hard
• Two new characterizations of path graphs
• Recognizing vertex intersection graphs of paths on bounded degree trees
• From path graphs to directed path graphs

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)