Cutting a tree with subgraph complementation is hard, except for some small trees
From MaRDI portal
Publication:6595520
DOI10.1002/JGT.23112zbMATH Open1546.05048MaRDI QIDQ6595520
R. Subashini, R. B. Sandeep, Dhanyamol Antony, Sagartanu Pal
Publication date: 30 August 2024
Published in: Journal of Graph Theory (Search for Journal in Brave)
Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A survey of the algorithmic aspects of modular decomposition
- Cluster editing with locally bounded modifications
- Recent developments on graphs of bounded clique-width
- Hardness of edge-modification problems
- Paw-free graphs
- On maximal independent sets of vertices in claw-free graphs
- Complement reducible graphs
- Two edge modification problems without polynomial kernels
- Cluster editing: kernelization based on edge cuts
- Cluster graph modification problems
- Recognizing \(P_ 3\)-structure: A switching approach
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- A polynomial kernel for diamond-free editing
- On subgraph complementation to \(H\)-free Graphs
- Subgraph complementation and minimum rank
- Subgraph complementation
- Incompressibility of \(H\)-free edge modification problems
- Compressing Bounded Degree Graphs
- On generating triangle-free graphs
- The complexity of some edge deletion problems
- Edge-Deletion Problems
- Hardness of Approximation for H -free Edge Modification Problems
- Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
- Independent Set in P5-Free Graphs in Polynomial Time
- On Switching to H‐Free Graphs
- Parameterized Algorithms
- Transitiv orientierbare Graphen
- Polynomial kernels for paw-free edge modification problems
- On perfect switching classes
- Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs
- Quasi-polynomial-time algorithm for independent set in \(P_t\)-free graphs via shrinking the space of induced paths
This page was built for publication: Cutting a tree with subgraph complementation is hard, except for some small trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6595520)
