Parameterizing edge modification problems above lower bounds (Q1635817): Difference between revisions

Revision as of 08:48, 12 July 2024

scientific article; zbMATH DE number 6605919

Parameterizing Edge Modification Problems Above Lower Bounds

Language	Label	Description	Also known as
English	Parameterizing edge modification problems above lower bounds	scientific article; zbMATH DE number 6605919	Parameterizing Edge Modification Problems Above Lower Bounds

Statements

instance of

scholarly article

0 references

title

Parameterizing edge modification problems above lower bounds (English)

0 references

Parameterizing Edge Modification Problems Above Lower Bounds (English)

0 references

zbMATH Open document ID

1386.68075

0 references

1386.68074

0 references

DOI

10.1007/s00224-016-9746-5

0 references

10.1007/978-3-319-34171-2_5

0 references

author

René van Bevern

0 references

Vincent Froese

0 references

Christian Komusiewicz

0 references

published in

Theory of Computing Systems

0 references

Computer Science – Theory and Applications

0 references

publication date

1 June 2018

0 references

25 July 2016

0 references

full work available at URL

https://arxiv.org/abs/1512.04047

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

NP-hard problem

0 references

fixed-parameter algorithm

0 references

subgraph packing

0 references

kernelization

0 references

graph-based clustering

0 references

feedback arc set

0 references

cluster editing

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

0 references

0 references

0 references

Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems

0 references

Kernels for feedback arc set in tournaments

0 references

Towards optimal and expressive kernelization for \(d\)-hitting set

0 references

A golden ratio parameterized algorithm for cluster editing

0 references

Going weighted: parameterized algorithms for cluster editing

0 references

On Generating Triangle-Free Graphs

0 references

Fixed-parameter tractability of graph modification problems for hereditary properties

0 references

A \(2k\) kernel for the cluster editing problem

0 references

Parameterized Algorithms

0 references

On Multiway Cut Parameterized above Lower Bounds

0 references

Fundamentals of parameterized complexity

0 references

Graph-Theoretic Concepts in Computer Science

0 references

Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee

0 references

Automated generation of search tree algorithms for hard graphs modification problems

0 references

Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament

0 references

Cluster editing with locally bounded modifications

0 references

NP-hard problems in hierarchical-tree clustering

0 references

The node-deletion problem for hereditary properties is NP-complete

0 references

Faster Parameterized Algorithms Using Linear Programming

0 references

Parameterizing above Guaranteed Values: MaxSat and MaxCut

0 references

Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes

0 references

Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem

0 references

Almost 2-SAT is fixed-parameter tractable

0 references

Cluster graph modification problems

0 references

Edge-Deletion Problems

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1635817

@@ Property / cites work @@
+Ranking Tournaments
@@ Property / cites work: Ranking Tournaments / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
+Normal rank
@@ Property / cites work @@
+Kernels for feedback arc set in tournaments
@@ Property / cites work: Kernels for feedback arc set in tournaments / rank @@
+Normal rank
@@ Property / cites work @@
+Towards optimal and expressive kernelization for \(d\)-hitting set
+Normal rank
@@ Property / cites work @@
+A golden ratio parameterized algorithm for cluster editing
+Normal rank
@@ Property / cites work @@
+Going weighted: parameterized algorithms for cluster editing
+Normal rank
@@ Property / cites work @@
+On Generating Triangle-Free Graphs
@@ Property / cites work: On Generating Triangle-Free Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed-parameter tractability of graph modification problems for hereditary properties
+Normal rank
@@ Property / cites work @@
+A \(2k\) kernel for the cluster editing problem
@@ Property / cites work: A \(2k\) kernel for the cluster editing problem / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithms
@@ Property / cites work: Parameterized Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+On Multiway Cut Parameterized above Lower Bounds
@@ Property / cites work: On Multiway Cut Parameterized above Lower Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Fundamentals of parameterized complexity
@@ Property / cites work: Fundamentals of parameterized complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Graph-Theoretic Concepts in Computer Science
@@ Property / cites work: Graph-Theoretic Concepts in Computer Science / rank @@
+Normal rank
@@ Property / cites work @@
+Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
+Normal rank
@@ Property / cites work @@
+Automated generation of search tree algorithms for hard graphs modification problems
+Normal rank
@@ Property / cites work @@
+Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
+Normal rank
@@ Property / cites work @@
+Cluster editing with locally bounded modifications
+Normal rank
@@ Property / cites work @@
+NP-hard problems in hierarchical-tree clustering
@@ Property / cites work: NP-hard problems in hierarchical-tree clustering / rank @@
+Normal rank
@@ Property / cites work @@
+The node-deletion problem for hereditary properties is NP-complete
+Normal rank
@@ Property / cites work @@
+Faster Parameterized Algorithms Using Linear Programming
+Normal rank
@@ Property / cites work @@
+Parameterizing above Guaranteed Values: MaxSat and MaxCut
+Normal rank
@@ Property / cites work @@
+Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
+Normal rank
@@ Property / cites work @@
+Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem
+Normal rank
@@ Property / cites work @@
+Almost 2-SAT is fixed-parameter tractable
@@ Property / cites work: Almost 2-SAT is fixed-parameter tractable / rank @@
+Normal rank
@@ Property / cites work @@
+Cluster graph modification problems
@@ Property / cites work: Cluster graph modification problems / rank @@
+Normal rank
@@ Property / cites work @@
+Edge-Deletion Problems
@@ Property / cites work: Edge-Deletion Problems / rank @@
+Normal rank