Maximum max-k-clique subgraphs in cactus subtree graphs

DOI10.1142/S1793830922501476MaRDI QIDQ6132893zbMATH OpenOpenAlexFDO

Authors 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)

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

Cites work

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

Cited in

(2)

• The maximum k-colorable subgraph problem for chordal graphs
• Maximum number of subtrees in cacti and block 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)