3D-interval-filament graphs

DOI10.1016/J.DAM.2007.08.006MaRDI QIDQ2462403zbMATH OpenOpenAlexFDO

Authors Fanica Gavril

Publication date 30 November 2007

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

Full work available at URL https://doi.org/10.1016/j.dam.2007.08.006

zbMATH Keywords

intersection graphoverlap graphinterval-filament graphsubtree-filament graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Maximum weight independent sets and cliques in intersection graphs of filaments
• On the structure of certain intersection graphs
• Equivalence of the filament and overlap graphs of subtrees of limited trees
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete

Cites work

• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 2192124 (Why is no real title available?)
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms for maximum weight induced paths
• Algorithms on circular-arc graphs
• Comparability graphs and intersection graphs
• Induced matchings in intersection graphs.
• Maximal sub-triangulation in pre-processing phylogenetic data
• Maximum independent set and maximum clique algorithms for overlap graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Permutation Graphs and Transitive Graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Thresholds for classes of intersection graphs
• Trapezoid graphs and generalizations, geometry and algorithms

Cited in

(14)

• A faster algorithm for maximum independent set on interval filament graphs
• Minimum weight feedback vertex sets in circle \(n\)-gon graphs and circle trapezoid graphs
• Minimum weight feedback vertex sets in circle graphs
• Algorithms on Subtree Filament Graphs
• On the structure of certain intersection graphs
• Equivalence of the filament and overlap graphs of subtrees of limited trees
• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
• Algorithms for induced biclique optimization problems
• Contractions in perfect graphs
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete

This page was built for publication: 3D-interval-filament graphs

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