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

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)

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

Cites work

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

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)