Algorithms for GA- H reduced graphs

DOI10.1016/J.JDA.2015.09.001MaRDI QIDQ891818zbMATH OpenOpenAlexFDO

Authors Fanica Gavril

Publication date 17 November 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2015.09.001

zbMATH Keywords

graph algorithmmaximum independent set\(\mathcal{H}\)-mixed graphsubgraph overlap graphsubtree filament graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Maximum weight independent sets and cliques in intersection graphs of filaments
• 3D-interval-filament graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• 3D-interval-filament graphs
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Algorithms for induced biclique optimization problems
• Algorithms for maximum weight induced paths
• Algorithms on Subtree Filament Graphs
• Algorithms on subgraph overlap graphs
• Brambles and independent packings in chordal graphs
• Comparability graphs and intersection graphs
• Covering and coloring polygon-circle graphs
• Independent packings in structured graphs
• Induced matchings in intersection graphs.
• Intersection graphs of Helly families of subtrees
• Maximum independent set and maximum clique algorithms for overlap graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Node-Deletion Problems on Bipartite Graphs
• On graphs with polynomially solvable maximum-weight clique problem
• Packing \(r\)-cliques in weighted chordal graphs
• Partitioning chordal graphs into independent sets and cliques
• Subtree filament graphs are subtree overlap 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

(4)

• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Maximum max-k-clique subgraphs in cactus subtree graphs
• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
• 3D-interval-filament graphs

This page was built for publication: Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs

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