Bounded-degree techniques accelerate some parameterized graph algorithms

DOI10.1007/978-3-642-11269-0_8MaRDI QIDQ3656854zbMATH OpenOpenAlexFDO

Authors Peter Damaschke

Publication date 14 January 2010

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-11269-0_8

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Even faster parameterized cluster deletion and cluster editing
• A parameterized algorithm for bounded-degree vertex deletion
• Faster parameterized algorithm for cluster vertex deletion
• A fast branching algorithm for cluster vertex deletion
• A fast branching algorithm for cluster vertex deletion

Cites work

• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
• Fixed-Parameter Algorithms for Cluster Vertex Deletion
• Fixed-parameter enumerability of cluster editing and related problems
• Going Weighted: Parameterized Algorithms for Cluster Editing
• Graph-modeled data clustering: Exact algorithms for clique generation
• Improved Upper Bounds for Partial Vertex Cover
• On two techniques of combining branching and treewidth
• Pathwidth of cubic graphs and exact algorithms
• The Cluster Editing Problem: Implementations and Experiments
• The union of minimal hitting sets: parameterized combinatorial bounds and counting

Cited in

(19)

• The cluster deletion problem for cographs
• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• Exact and heuristic solution approaches for the cluster deletion problem on general graphs
• Parameterized algorithms for min-max 2-cluster editing
• Cluster deletion revisited
• Speeding up dynamic transitive closure for bounded degree graphs
• Parameterized algorithms for cluster vertex deletion on degree-4 graphs and general graphs
• A novel branching strategy for parameterized graph modification problems
• Even faster parameterized cluster deletion and cluster editing
• Cluster editing
• A golden ratio parameterized algorithm for cluster editing
• Parameterized algorithms for editing to uniform cluster graph
• Improved parameterized algorithms for cluster vertex deletion
• Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
• Smaller kernels for 3-leaf power modifications problems
• An improved parameterized algorithm for the p-cluster vertex deletion problem
• A parameterized algorithm for bounded-degree vertex deletion

This page was built for publication: Bounded-degree techniques accelerate some parameterized graph algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3656854)