Contraction Blockers for Graphs with Forbidden Induced Paths

DOI10.1007/978-3-319-18173-8_14zbMath1459.68156OpenAlexW2266980279MaRDI QIDQ2947020

Öznur Yaşar Diner, Bernard Ries, Daniël Paulusma, Christophe Picouleau

Publication date: 21 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/14241/1/14241.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Reducing the chromatic number by vertex or edge deletions ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Reducing the domination number of graphs via edge contractions and vertex deletions ⋮ Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Unnamed Item ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Blocking total dominating sets via edge contractions ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut ⋮ Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions ⋮ Using edge contractions to reduce the semitotal domination number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Parameterized complexity of three edge contraction problems with degree constraints
• Blockers for the stability number and the chromatic number
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• Complement reducible graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• On the NP-hardness of edge-deletion and -contraction problems
• Incidence matrices and interval graphs
• Hadwiger Number of Graphs with Small Chordality
• Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
• A Linear Recognition Algorithm for Cographs
• Four classes of perfectly orderable graphs
• Graph Classes: A Survey
• Minimum vertex blocker clique problem
• The Pathwidth and Treewidth of Cographs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Obtaining a Bipartite Graph by Contracting Few Edges

This page was built for publication: Contraction Blockers for Graphs with Forbidden Induced Paths