Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
type: Item
instance of: scholarly article
title: Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
zbMATH Open document ID: 1390.68354
author: Mathias Weller
author: Annie Chateau
author: Clément Dallard
author: Rodolphe Giroudeau
published in: Algorithmica
publication date: 2018-06-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 92D10
zbMATH DE Number: 6879863
zbMATH Keywords: complexity
zbMATH Keywords: approximation
zbMATH Keywords: lower bound
zbMATH Keywords: kernel
zbMATH Keywords: scaffolding
describes a project that uses: SOPRA
MaRDI profile type: Publication
full work available at URL: s00453-018-0405-x
OpenAlex ID: W2788483986
cites work: A complexity and approximation framework for the maximization scaffolding problem
cites work: Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
cites work: Blockers for the stability number and the chromatic number
cites work: A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
cites work: Q4291429
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Partitions of graphs into one or two independent sets and cliques
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Fundamentals of parameterized complexity
cites work: Q4198056
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Q4904144
cites work: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
cites work: On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs
cites work: Q4414647
DOI: 10.1007/S00453-018-0405-X
description: scientific article; zbMATH DE number 6879863