A Note on the Minimum H-Subgraph Edge Deletion

DOI10.1142/S0129054115500227zbMATH Open1321.05263DBLPjournals/ijfcs/GrigorievMU15OpenAlexW2247427276WikidataQ57338942 ScholiaQ57338942MaRDI QIDQ2947962FDOQ2947962

Authors: Alexander Grigoriev, Bert Marchal, Natalya Usotskaya 

Publication date: 29 September 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

Recommendations

• Minimum \(H\)-decompositions of graphs: edge-critical case
• Publication:3469115
• Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems
• Algorithms for the minimum edge cover of \(H\)-subgraphs of a graph
• Minimum \(H\)-decompositions of graphs
• On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
• EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
• On making a distinguished vertex minimum degree by vertex deletion
• The complexity of some edge deletion problems
• Approximation algorithms for minimum chain vertex deletion

zbMATH Keywords

bounded treewidth\(H\)-free graphminimum edge deletion

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• A partial k-arboretum of graphs with bounded treewidth
• Easy problems for tree-decomposable graphs
• Efficient Planarity Testing
• Approximation algorithms for NP-complete problems on planar graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithms for graphs embeddable with few crossings per edge
• Graph minors. III. Planar tree-width
• On the complexity of embedding planar graphs to minimize certain distance measures
• Diameter and treewidth in minor-closed graph families
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Edge-Deletion Problems
• A Practical Approach to Courcelle's Theorem

Cited In (2)

• Algorithms for the minimum edge cover of \(H\)-subgraphs of a graph
• Deleting edges to restrict the size of an epidemic: a new application for treewidth

This page was built for publication: A Note on the Minimum H-Subgraph Edge Deletion

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