BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES

DOI10.1142/S1793830912500085zbMath1247.05243OpenAlexW2024836278MaRDI QIDQ2905308

James Nastos, Yong Gao

Publication date: 27 August 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

cographsfixed-parameter tractabilitygraph modificationedge-deletionquasi-threshold graphsbounded search treetrivially perfect graphs

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Linear-time minimal cograph editing, Hierarchical and modularly-minimal vertex colorings, Parameterized algorithms for edge biclique and related problems, On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}, A survey of parameterized algorithms and the complexity of edge modification, Spiders can be recognized by counting their legs, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, Edge deletion problems: branching facilitated by modular decomposition, Defining and identifying cograph communities in complex networks, Faster algorithms for cograph edge modification problems

Cites Work

• An efficient fixed-parameter algorithm for 3-hitting set
• Matrix multiplication via arithmetic progressions
• Parameterized algorithms for \(d\)-hitting set: the weighted case
• Characterizing and computing minimal cograph completions
• Modular decomposition and transitive orientation
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Automated generation of search tree algorithms for hard graphs modification problems
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• On a property of the class of n-colorable graphs
• BetweenO(nm) andO(n^alpha)
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A Linear Recognition Algorithm for Cographs
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Graph Classes: A Survey
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs