Intersection graphs of Helly families of subtrees

DOI10.1016/0166-218X(94)00136-2zbMath0856.05084OpenAlexW2071616675MaRDI QIDQ1917300

Fanica Gavril

Publication date: 7 July 1996

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00136-2

zbMATH Keywords

intersection graphsubtreesHelly family

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75)

Related Items (13)

Families of induced trees and their intersection graphs ⋮ Maximum weight independent sets and cliques in intersection graphs of filaments ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Unnamed Item ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ Intersection representations of matrices by subtrees and unicycles on graphs ⋮ Intersection graphs of non-crossing paths ⋮ On \(H\)-topological intersection graphs ⋮ Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs ⋮ Intersection graphs of \(k\)-acyclic families of subtrees and relational database query processing. ⋮ Algorithms for maximum weight induced paths

Cites Work

• Unnamed Item
• A linear algorithm for the group path problem on chordal graphs
• Efficient reduction for path problems on circular-arc graphs
• Intersection graphs of paths in a tree
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Triangulated graphs and the elimination process
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Generating the maximum spanning trees of a weighted graph
• On the tree representation of chordal graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms on circular-arc graphs
• Coloring a Family of Circular Arcs
• A New Algorithm for Generating All the Maximal Independent Sets
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Characterizing circular-arc graphs

This page was built for publication: Intersection graphs of Helly families of subtrees