Maximum max-k-clique subgraphs in cactus subtree graphs

DOI10.1142/S1793830922501476zbMATH Open1516.05209OpenAlexW4298145080MaRDI QIDQ6132893FDOQ6132893

Fanica Gavril

Publication date: 15 July 2023

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830922501476

zbMATH Keywords

maximum induced forestminimum feedback vertex setcactus subtree graphmaximum induced bipartite graphmaximum max-\(k\)-clique subgraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cites Work

• Decomposition by clique separators
• Comparability graphs and intersection graphs
• Linear-time recognition of circular-arc graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms on circular-arc graphs
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Algorithms for maximum weight induced paths
• Intersection graphs of Helly families of subtrees
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Algorithms on clique separable graphs
• Induced matchings in intersection graphs.
• Covering and coloring polygon-circle graphs
• Title not available (Why is that?)
• An algorithm for finding clique cut-sets
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Title not available (Why is that?)
• Subtree filament graphs are subtree overlap graphs
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Algorithms on Subtree Filament Graphs
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
• Approximating the throughput of multiple machines under real-time scheduling
• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs

Cited In (1)

• Maximum number of subtrees in cacti and block graphs

   Recommendations

• The maximum k-colorable subgraph problem for chordal graphs 👍 👎
• On the Maximum Weight Clique Problem 👍 👎
• Algorithms and Computation 👍 👎
• Minmax subtree cover problem on cacti 👍 👎
• An optimal algorithm to find maximum independent set and maximum 2-independent set on cactus graphs 👍 👎

This page was built for publication: Maximum max-k-clique subgraphs in cactus subtree graphs

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