Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
type: Item
instance of: scholarly article
title: Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
zbMATH Open document ID: 1414.05128
author: Neeldhara Misra
author: Fahad Panolan
author: Ashutosh Rai
author: Venkatesh Raman
author: Saket Saurabh
published in: Algorithmica
publication date: 2019-01-11T00:00:00Z
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 7000177
zbMATH Keywords: maximum induced subgraphs
zbMATH Keywords: perfect graphs
zbMATH Keywords: co-chordal graphs
zbMATH Keywords: randomized FPT algorithms
zbMATH Keywords: polynomial kernel lower bounds
MaRDI profile type: Publication
full work available at URL: s00453-018-0431-8
OpenAlex ID: W2795452868
cites work: Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
cites work: Solving MAX-\(r\)-SAT above a tight lower bound
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: Kernelization: New Upper and Lower Bound Techniques
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: Enumerating maximal independent sets with applications to graph colouring.
cites work: Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Kernelization Lower Bounds Through Colors and IDs
cites work: Q4503944
cites work: Kernelization and Sparseness: the case of Dominating Set
cites work: Improved FPT algorithms for weighted independent set in bull-free graphs
cites work: Parametrized complexity theory.
cites work: On the minimum feedback vertex set problem: Exact and enumeration algorithms
cites work: Bidimensionality and Geometric Graphs
cites work: Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Faster parameterized algorithms for deletion to split graphs
cites work: Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
cites work: A randomized polynomial kernel for subset feedback vertex set
cites work: Parameterized complexity of finding subgraphs with hereditary properties.
cites work: Representative Sets and Irrelevant Vertices
cites work: Compression via Matroids
cites work: Q3320435
cites work: Q4231923
cites work: Q5710169
cites work: Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
cites work: Efficient exact algorithms through enumerating maximal independent sets and other techniques
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
cites work: A polynomial Turing-kernel for weighted independent set in bull-free graphs
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: The maximum k-colorable subgraph problem for chordal graphs
DOI: 10.1007/S00453-018-0431-8
description: scientific article; zbMATH DE number 7000177