A faster algorithm to recognize undirected path graphs

DOI10.1016/0166-218X(93)90116-6zbMath0770.68096MaRDI QIDQ2367409

Alejandro A. Schäffer

Publication date: 10 August 1993

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

zbMATH Keywords

intersection graphchordal graphsundirected path graphs

Mathematics Subject Classification ID

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

Related Items (12)

Two new characterizations of path graphs ⋮ The vertex leafage of chordal graphs ⋮ Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs ⋮ Intersection representations of matrices by subtrees and unicycles on graphs ⋮ Intersection graphs of non-crossing paths ⋮ From Path Graphs to Directed Path Graphs ⋮ Recognizing vertex intersection graphs of paths on bounded degree trees ⋮ Characterizing path graphs by forbidden induced subgraphs ⋮ Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage ⋮ The forbidden subgraph characterization of directed vertex graphs ⋮ Extending partial representations of subclasses of chordal graphs ⋮ Recognition algorithm for intersection graphs of edge disjoint paths in a tree

Cites Work

• Unnamed Item
• Unnamed Item
• Intersection graphs of paths in a tree
• The maximum k-colorable subgraph problem for chordal graphs
• 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
• A characterisation of rigid circuit graphs
• Intersection representations of graphs by arcs
• Triangulated graphs and the elimination process
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational database schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The NP-completeness column: an ongoing guide
• 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 Characterization of Comparability Graphs and of Interval Graphs

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