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)
- Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
- Backbone coloring of graphs with galaxy backbones
- Backbone coloring of graphs with galaxy backbones
- Title not available (Why is that?)
- On girth and the parameterized complexity of token sliding and token jumping
- On computing the Hamiltonian index of graphs
- Parameterized complexity of the anchored \(k\)-core problem for directed graphs
- A randomized algorithm for long directed cycle
- Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths
- On the parameterized complexity of reconfiguration of connected dominating sets
- On finding rainbow and colorful paths
- Token sliding on split graphs
- Token sliding on split graphs
- Designing FPT algorithms for cut problems using randomized contractions
- On critical node problems with vulnerable vertices
- Editing to a connected graph of given degrees
- On the vertex cover \(P_3\) problem parameterized by treewidth
- On two extensions of equimatchable graphs
- On polynomial kernels for sparse integer linear programs
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Parameterized complexity of weighted multicut in trees
- Parameterized complexity of multicut in weighted trees
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- Improved FPT algorithms for weighted independent set in bull-free graphs
- An improved kernel for max-bisection above tight lower bound
- Multi-budgeted directed cuts
- Multi-budgeted directed cuts
- The mixed Chinese postman problem parameterized by pathwidth and treedepth
- On the parameterized complexity of compact set packing
- On the complexity of the identifiable subgraph problem, revisited
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Are there any nicely structured preference profiles nearby?
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Structured connectivity augmentation
- Acyclicity in edge-colored graphs
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- On structural parameterizations of star coloring
- On algorithms employing treewidth for \(L\)-bounded cut problems
- On the complexity of connection games
- A faster parameterized algorithm for Group Feedback Edge Set
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
- Kernelization of cycle packing with relaxed disjointness constraints
- Subexponential parameterized algorithms for graphs of polynomial growth
- Complexity of secure sets
- Parity permutation pattern matching
- On the parameterized complexity of reconfiguration problems
- On optimal approximability results for computing the strong metric dimension
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Prices matter for the parameterized complexity of shift bribery
- On Computing the Hamiltonian Index of Graphs
- Parameterized complexity of configuration integer programs
- \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments
- Improved approximation algorithms for two-stage flowshops scheduling problem
- Subset feedback vertex set on graphs of bounded independent set size
- Complete colourings of hypergraphs
- An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
- Parameterized complexity of satisfactory partition problem
- Approximation in (Poly-) Logarithmic Space
- Title not available (Why is that?)
- On the parameterized complexity of maximum degree contraction problem
- On the parameterized complexity of b-\textsc{chromatic number}
- Perfect forests in graphs and their extensions
- On the Parameterized Complexity of Maximum Degree Contraction Problem.
- On the parameterized tractability of the just-in-time flow-shop scheduling problem
- Title not available (Why is that?)
- NP-completeness results for partitioning a graph into total dominating sets
- Weighted proper orientations of trees and graphs of bounded treewidth
- Graph editing to a given degree sequence
- Graph editing to a given degree sequence
- Assigning times to minimise reachability in temporal graphs
- On the complexity of singly connected vertex deletion
- Triangle-free planar graphs with small independence number
- On the maximum cardinality cut problem in proper interval graphs and related graph classes
- Explicit linear kernels for packing problems
- Subgraph isomorphism on graph classes that exclude a substructure
- On the computational complexity of length- and neighborhood-constrained path problems
- Fractals for kernelization lower bounds
- 1.5D terrain guarding problem parameterized by guard range
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Parameterized complexity of strip packing and minimum volume packing
- Complexity of rainbow vertex connectivity problems for restricted graph classes
- Minimum reload cost graph factors
- Reoptimization of parameterized problems
- Partition on trees with supply and demand: kernelization and algorithms
- Fixed-parameter algorithms for DAG partitioning
- Kernels for packing and covering problems
- An ETH-Tight Exact Algorithm for Euclidean TSP
- Title not available (Why is that?)
- \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
- The complexity of finding effectors
- Hitting forbidden minors: approximation and kernelization
- Parameterized complexity of team formation in social networks
- Parameterized complexity of team formation in social networks
- Tournaments and the strong Erdős-Hajnal property
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Turing kernelization for finding long paths and cycles in restricted graph classes
- Cyclability in graph classes
- On the optimality of pseudo-polynomial algorithms for integer programming
- Approximation in (poly-) logarithmic space
- On the optimality of pseudo-polynomial algorithms for integer programming
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)
