Parameterized algorithms
DOI10.1007/978-3-319-21275-3zbMATH Open1334.90001OpenAlexW2914414140WikidataQ56805475 ScholiaQ56805475MaRDI QIDQ5502162FDOQ5502162
Authors: Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh 
Publication date: 17 August 2015
Full work available at URL: https://doi.org/10.1007/978-3-319-21275-3
Recommendations
treewidthlower boundskernelizationmatroidsiterative compressionbounded search treescuts and separatorsdynamic programming on treewidthExponential-Time Hypothesisrandomized methods in parameterized algorithms
Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) General applied mathematics (00A69) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Abstract computational complexity for mathematical programming problems (90C60) Mathematics in general (00A05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematics in general (00-01) Mathematics for nonmathematicians (engineering, social sciences, etc.) (00A06) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01)
Cited In (only showing first 100 items - show all)
- A parameterized complexity view on collapsing \(k\)-cores
- On the proper orientation number of chordal graphs
- A parameterized complexity view on collapsing \(k\)-cores
- Compactors for parameterized counting problems
- Practical access to dynamic programming on tree decompositions
- A parameterized algorithm for subset feedback vertex set in tournaments
- A Retrospective on (Meta) Kernelization
- Fine-grained complexity of safety verification
- Optimal data reduction for graph coloring using low-degree polynomials
- The maximum binary tree problem
- Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- An improved FPT algorithm for independent feedback vertex set
- Planarizing graphs and their drawings by vertex splitting
- Parameterized Complexity of $$(A,\ell )$$-Path Packing
- Parameterizing edge modification problems above lower bounds
- On the parameterized complexity of the expected coverage problem
- Corrigendum to: ``Advice classes of parameterized tractability
- Approximation and kernelization for chordal vertex deletion
- Reconfiguration on nowhere dense graph classes
- A width parameter useful for chordal and co-comparability graphs
- Counting problems in parameterized complexity
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- The parameterized hardness of the \(k\)-center problem in transportation networks
- On the computational complexity of the bipartizing matching problem
- Parameterized complexity of machine scheduling: 15 open problems
- FPT and kernelization algorithms for the induced tree problem
- A fixed-parameter perspective on \#BIS
- A fixed-parameter perspective on \#BIS
- Space-efficient vertex separators for treewidth
- Finding cactus roots in polynomial time
- On the complete width and edge clique cover problems
- Dynamic parameterized problems
- Rank reduction of oriented graphs by vertex and edge deletions
- Stable matching games: manipulation via subgraph isomorphism
- Approximability of clique transversal in perfect graphs
- On the parameterized complexity of contraction to generalization of trees
- Stable matchings with covering constraints: a complete computational trichotomy
- Parameter analysis for guarding terrains
- Parameterized counting of trees, forests and matroid bases
- Faster parameterized algorithm for pumpkin vertex deletion set
- Parameterized low-rank binary matrix approximation
- Parameterized \(k\)-clustering: tractability island
- Parameterized dynamic cluster editing
- On the complexity of algorithms for detecting \(k\)-length negative cost cycles
- Mim-width. II. The feedback vertex set problem
- A multivariate analysis of the strict terminal connection problem
- FPT algorithms for generalized feedback vertex set problems
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- Twins in Subdivision Drawings of Hypergraphs
- Dual parameterization of weighted coloring
- Group activity selection with few agent types
- Dual parameterization of weighted coloring
- Fréchet distance between a line and avatar point set
- Lower bounds for the graph homomorphism problem
- Defensive alliances in graphs
- On rectangle intersection graphs with stab number at most two
- Parameterized Complexity of Conflict-Free Graph Coloring
- Parameterized complexity of minimum membership dominating set
- Parameterized complexity of minimum membership dominating set
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Dynamic coloring on restricted graph classes
- Parameterized complexity of \((A,\ell)\)-path packing
- Ruling out FPT algorithms for weighted coloring on forests
- Metric Dimension of Bounded Tree-length Graphs
- Present-biased optimization
- Consensus strings with small maximum distance and small distance sum
- Consensus strings with small maximum distance and small distance sum
- On structural parameterizations of firefighting
- Title not available (Why is that?)
- A linear kernel for finding square roots of almost planar graphs
- Computing square roots of graphs with low maximum degree
- Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
- Finding disjoint paths on edge-colored graphs: a multivariate complexity analysis
- An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
- Best-case and worst-case sparsifiability of Boolean CSPs
- Parameterized complexity of independent set in H-free graphs
- The parameterised complexity of computing the maximum modularity of a graph
- Title not available (Why is that?)
- The Maximum Binary Tree Problem.
- Structural parameterizations of clique coloring
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Component order connectivity in directed graphs
- Component order connectivity in directed graphs
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Parameterized algorithms for conflict-free colorings of graphs
- Eternal vertex cover on bipartite graphs
- On the approximability of path and cycle problems in arc-dependent networks
- Edge bipartization faster than \(2^k\)
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- Parameterized algorithms for list \(K\)-cycle
- The minimum feasible tileset problem
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
- Counting linear extensions: parameterizations by treewidth
- Combinatorial \(n\)-fold integer programming and applications
- Combinatorial \(n\)-fold integer programming and applications
- Structural parameterization for minimum conflict-free colouring
This page was built for publication: Parameterized algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502162)
