Intersection graphs of Helly families of subtrees

DOI10.1016/0166-218X(94)00136-2MaRDI QIDQ1917300zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1002178
• Helly type theorem and graphs
• Intersection graphs of concatenable subtrees of graphs

Cites work

• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A New Algorithm for Generating All the Maximal Independent Sets
• A linear algorithm for the group path problem on chordal graphs
• Algorithms on circular-arc graphs
• Characterizing circular-arc graphs
• Coloring a Family of Circular Arcs
• Efficient reduction for path problems on circular-arc graphs
• Generating the maximum spanning trees of a weighted graph
• Intersection graphs of paths in a tree
• On the tree representation of chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Complexity of Coloring Circular Arcs and Chords
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Triangulated graphs and the elimination process

Cited in

(14)

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

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

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