Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases (Q1635706): Difference between revisions

@@ Property / DOI @@
-.1007/s00453-018-0405-x
@@ Property / DOI: 10.1007/s00453-018-0405-x / rank @@
-Normal rank
@@ Property / describes a project that uses @@
+SOPRA
@@ Property / describes a project that uses: SOPRA / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00453-018-0405-x
+Normal rank
@@ Property / OpenAlex ID @@
+W2788483986
@@ Property / OpenAlex ID: W2788483986 / rank @@
+Normal rank
@@ Property / cites work @@
+A complexity and approximation framework for the maximization scaffolding problem
+Normal rank
@@ Property / cites work @@
+Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
+Normal rank
@@ Property / cites work @@
+Blockers for the stability number and the chromatic number
+Normal rank
@@ Property / cites work @@
+A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
+Normal rank
@@ Property / cites work @@
+Q4291429
@@ Property / cites work: Q4291429 / rank @@
+Normal rank
@@ Property / cites work @@
+Kernelization Lower Bounds by Cross-Composition
@@ Property / cites work: Kernelization Lower Bounds by Cross-Composition / rank @@
+Normal rank
@@ Property / cites work @@
+Partitions of graphs into one or two independent sets and cliques
+Normal rank
@@ Property / cites work @@
+Tight lower bounds for certain parameterized NP-hard problems
+Normal rank
@@ Property / cites work @@
+Fundamentals of parameterized complexity
@@ Property / cites work: Fundamentals of parameterized complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Q4904144
@@ Property / cites work: Q4904144 / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
+Normal rank
@@ Property / cites work @@
+On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs
+Normal rank
@@ Property / cites work @@
+Q4414647
@@ Property / cites work: Q4414647 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S00453-018-0405-X
@@ Property / DOI: 10.1007/S00453-018-0405-X / rank @@
+Normal rank