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)- Conflict-free coloring bounds on open neighborhoods
- Combinatorial \(n\)-fold integer programming and applications
- Structural parameterization for minimum conflict-free colouring
- 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
- 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?)
- Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues
- 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
- On the parameterized complexity of \([1,j]\)-domination problems
- Consensus patterns (probably) has no EPTAS
- 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
- Parameterized algorithms for the happy set problem
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- Structural parameterizations of budgeted graph coloring
- 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?)
- 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
- \(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
- Coloring problems on bipartite graphs of small diameter
- On the universal steganography of optimal rate
- On structural parameterizations of load coloring
- Parameterized complexity of d-hitting set with quotas
- The balanced satisfactory partition problem
- Sorting by multi-cut rearrangements
- Fast exact algorithms using Hadamard product of polynomials
- Pattern matching in doubling spaces
- Parameterized complexity of categorical clustering with size constraints
- A Retrospective on (Meta) Kernelization
- Constructing tree decompositions of graphs with bounded gonality
- Backbone coloring of graphs with galaxy backbones
- Backbone coloring of graphs with galaxy backbones
- On computing the Hamiltonian index of graphs
- scientific article; zbMATH DE number 7559382 (Why is no real title available?)
- On computing large temporal (unilateral) connected components
- Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
- On subgraph complementation to \(H\)-free graphs
- Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
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)
