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