Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs

DOI10.1016/j.jda.2015.09.001zbMath1326.05153OpenAlexW1921470280MaRDI QIDQ891818

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)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Trapezoid graphs and generalizations, geometry and algorithms
• Packing \(r\)-cliques in weighted chordal graphs
• Brambles and independent packings in chordal graphs
• Comparability graphs and intersection graphs
• Thresholds for classes of intersection graphs
• Covering and coloring polygon-circle graphs
• Maximum independent set and maximum clique algorithms for overlap graphs
• Induced matchings in intersection graphs.
• Algorithms for maximum weight induced paths
• Partitioning chordal graphs into independent sets and cliques
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Intersection graphs of Helly families of subtrees
• Algorithms for induced biclique optimization problems
• Subtree filament graphs are subtree overlap graphs
• 3D-interval-filament graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Independent packings in structured graphs
• ALGORITHMS ON SUBGRAPH OVERLAP GRAPHS
• Algorithms on Subtree Filament Graphs
• On graphs with polynomially solvable maximum-weight clique problem
• Node-Deletion Problems on Bipartite Graphs