Subtree filament graphs are subtree overlap graphs

DOI10.1016/J.IPL.2007.07.004MaRDI QIDQ2380028zbMATH OpenOpenAlexFDO

Authors Jessica Enright, Lorna Stewart

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.07.004

zbMATH Keywords

graph algorithmsoverlap graphcombinatorial problemssubtree filament graphsubtree overlap graph

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Algorithmic graph theory and perfect graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Containment Graphs, Posets, and Related Classes of Graphs
• Graph Classes: A Survey
• Maximum independent set and maximum clique algorithms for overlap graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Sur deux propriétés des classes d'ensembles
• The Complexity of Coloring Circular Arcs and Chords
• The complexity of domination problems in circle graphs
• The edge intersection graphs of paths in a tree

Cited in

(9)

• Towards a comprehensive theory of conflict-tolerance graphs
• Algorithms on Subtree Filament Graphs
• On-line approach to off-line coloring problems on graphs with geometric representations
• Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
• Maximum max-k-clique subgraphs in cactus subtree graphs
• Recognising the overlap graphs of subtrees of restricted trees is hard
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
• Algorithms for induced biclique optimization problems

This page was built for publication: Subtree filament graphs are subtree overlap graphs

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