Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
type: Item
instance of: scholarly article
zbMATH Open document ID: 1247.05243
DOI: 10.1142/S1793830912500085
author: James Nastos
author: Yong Gao
published in: Discrete Mathematics, Algorithms and Applications
publication date: 2012-08-27T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 6072546
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: edge-deletion
zbMATH Keywords: graph modification
zbMATH Keywords: cographs
zbMATH Keywords: trivially perfect graphs
zbMATH Keywords: quasi-threshold graphs
zbMATH Keywords: bounded search tree
MaRDI profile type: Publication
cites work: Graph Classes: A Survey
cites work: A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: Matrix multiplication via arithmetic progressions
cites work: A Linear Recognition Algorithm for Cographs
cites work: Parameterized algorithms for \(d\)-hitting set: the weighted case
cites work: On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
cites work: Automated generation of search tree algorithms for hard graphs modification problems
cites work: Recognizing $P_4 $-Sparse Graphs in Linear Time
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: BetweenO(nm) andO(nalpha)
cites work: Characterizing and computing minimal cograph completions
cites work: Modular decomposition and transitive orientation
cites work: An efficient fixed-parameter algorithm for 3-hitting set
cites work: On a property of the class of n-colorable graphs
cites work: Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
full work available at URL: s1793830912500085
OpenAlex ID: W2024836278
title: Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
description: scientific article; zbMATH DE number 6072546