Parameterized algorithms
From MaRDI portal
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)- Conflict-free coloring bounds on open neighborhoods
- Combinatorial \(n\)-fold integer programming and applications
- Structural parameterization for minimum conflict-free colouring
- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
- Multivariate algorithmics for finding cohesive subnetworks
- Approximation in (poly-) logarithmic space
- On the optimality of pseudo-polynomial algorithms for integer programming
- Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic Issues
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- On the proper orientation number of chordal graphs
- A parameterized complexity view on collapsing \(k\)-cores
- Compactors for parameterized counting problems
- Minimum eccentricity shortest path problem with respect to structural parameters
- Minimum eccentricity shortest path problem with respect to structural parameters
- Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
- Efficient polynomial-time approximation scheme for the genus of dense graphs
- Parameterized complexity of conflict-free matchings and paths
- Revisiting the parameterized complexity of maximum-duo preservation string mapping
- Lossy kernelization of same-size clustering
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- On the optimality of pseudo-polynomial algorithms for integer programming
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- Parameterised algorithms for deletion to classes of DAGs
- A multistage view on 2-satisfiability
- The parameterized complexity of the minimum shared edges problem
- scientific article; zbMATH DE number 7278041 (Why is no real title available?)
- Parameterized algorithms for multi-label periodic temporal graph realization
- Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
- Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. II: Hardness results
- Parameterized covering in semi-ladder-free hypergraphs
- Maintaining \(\mathrm{CMSO}_2\) properties on dynamic structures with bounded feedback vertex number
- Packing arc-disjoint cycles in oriented graphs
- A theoretical and computational analysis of full strong-branching
- Parameterized complexity for iterated type partitions and modular-width
- List homomorphism: beyond the known boundaries
- Parameterised and fine-grained subgraph counting, modulo 2
- The iteration time and the general position number in graph convexities
- On the parameterized complexity of \([1,j]\)-domination problems
- Consensus patterns (probably) has no EPTAS
- Approximately interpolating between uniformly and non-uniformly polynomial kernels
- Parameterized complexity of incomplete connected fair division
- Parameterized complexity of biclique contraction and balanced biclique contraction
- On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
- A parameterized complexity view on collapsing \(k\)-cores
- How bad is the freedom to Flood-It?
- On the thinness of trees
- A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
- Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
- How to Secure Matchings Against Edge Failures
- Modification to Planarity is Fixed Parameter Tractable
- Algorithmic aspects of the maximum colorful arborescence problem
- Red blue set cover problem on axis-parallel hyperplanes and other objects
- On guarding orthogonal polygons with sliding cameras
- Kernelization for edge triangle packing and covering via a discharging method
- On the size of minimal separators for treedepth decomposition
- Being an influencer is hard: the complexity of influence maximization in temporal graphs with a fixed source
- The multicolored graph realization problem
- On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
- Practical access to dynamic programming on tree decompositions
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Exact matching: correct parity and FPT parameterized by independence number
- FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set
- Recognizing unit multiple intervals is hard
- Parameterized algorithms for the happy set problem
- Dominator coloring and CD coloring in almost cluster graphs
- Maximizing utilitarian and egalitarian welfare of fractional hedonic games on tree-like graphs
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- Structural parameterizations of budgeted graph coloring
- Weighted connected matchings
- Exact and approximation algorithms for sensor placement against DDoS attacks
- scientific article; zbMATH DE number 7559421 (Why is no real title available?)
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- On two-handed planar assembly partitioning with connectivity constraints
- Homology localization through the looking-glass of parameterized complexity theory
- How to Secure Matchings against Edge Failures
- 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 finding rainbow and colorful paths
- A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
- Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- A parameterized algorithm for subset feedback vertex set in tournaments
- On the parameterized complexity of reconfiguration of connected dominating sets
- On girth and the parameterized complexity of token sliding and token jumping
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- On the complexity of solution extension of optimization problems
- Communication complexity of pairs of graph families with applications
- On the maximum colorful arborescence problem and color hierarchy graph structure
- Numerical experiments with LP formulations of the maximum clique problem
- Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
- Cluster editing with vertex splitting
- \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
- Quick but odd growth of cacti
- A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
- New algorithms for minimizing the weighted number of tardy jobs on a single machine
- A (2 + ) k-vertex kernel for the dual coloring problem
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)
