Triangle-covered graphs: algorithms, complexity, and structure

DOI10.1016/J.TCS.2026.115848MaRDI QIDQ7229616zbMATH OpenFDO

Authors Amirali Madani, Anil Maheshwari, Babak Miraftab, Paweł Żyliński

Publication date 16 April 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115848

zbMATH Keywords

approximation algorithmscomputational complexityedge modification problemsgraph algorithmsoptimal algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A 2k kernel for the cluster editing problem
• A more relaxed model for graph-based data clustering: s-plex cluster editing
• A note on finding the bridges of a graph
• A survey of parameterized algorithms and the complexity of edge modification
• Algorithms and hardness results for the (3, 1)-cover problem
• Analytical approach to parallel repetition
• Bounds and algorithms for graph trusses
• Building large \(k\)-cores from sparse graphs
• Can we create large \(k\)-cores by adding few edges?
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Concentration of Measure for the Analysis of Randomized Algorithms
• Extremal graphs with local covering conditions

This page was built for publication: Triangle-covered graphs: algorithms, complexity, and structure

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