Parameterized algorithms
From MaRDI portal
Publication:5502162
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)
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- On the parameterized tractability of single machine scheduling with rejection
- Title not available (Why is that?)
- Title not available (Why is that?)
- Paths to trees and cacti
- Parameterized approximation algorithms for bidirected Steiner network problems
- Parameterized algorithms for edge biclique and related problems
- Strong triadic closure in cographs and graphs of low maximum degree
- Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
- Adapting the directed grid theorem into an \textsf{FPT} algorithm
- Evaluation and enumeration problems for regular path queries
- \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
- On the approximate compressibility of connected vertex cover
- The inverse Voronoi problem in graphs. I: Hardness
- Sliding window temporal graph coloring
- Fixed parameter tractability of graph deletion problems over data streams
- Parameterized complexity of \textsc{maximum edge colorable subgraph}
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- Title not available (Why is that?)
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- In)approximability of Maximum Minimal FVS
- Hardness and tractability of the \(\gamma\)-complete subgraph problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Enumeration and maximum number of maximal irredundant sets for chordal graphs
- Representative families for matroid intersections, with applications to location, packing, and covering problems
- Provision-after-wait with preferences ordered by difference: tighter complexity and better approximation
- A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
- Analyzing clustering and partitioning problems in selected VLSI models
- On structural parameterizations of the edge disjoint paths problem
- Parameterized counting of partially injective homomorphisms
- A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
- Finding Temporal Paths Under Waiting Time Constraints.
- Solving partition problems almost always requires pushing many vertices around
- Parameterized (approximate) defective coloring
- On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- Computing maximum matchings in temporal graphs
- Faster parameterized algorithm for cluster vertex deletion
- On the complexity of the smallest grammar problem over fixed alphabets
- Reducing graph transversals via edge contractions
- Faster deterministic algorithm for cactus vertex deletion
- Parameterized (approximate) defective coloring
- Finding cliques in social networks: a new distribution-free model
- Finding Hamiltonian cycle in graphs of bounded tree-width: experimental evaluation
- Parameterized aspects of strong subgraph closure
- What Is Known About Vertex Cover Kernelization?
- Parameterized algorithms for book embedding problems
- On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
- Coloring temporal graphs
- Metric dimension parameterized by treewidth
- Subexponential-time algorithms for finding large induced sparse subgraphs
- On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
- Minimum fill-in: inapproximability and almost tight lower bounds
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- The power of cut-based parameters for computing edge-disjoint paths
- Maximum minimal vertex cover parameterized by vertex cover
- Deleting vertices to graphs of bounded genus
- Grundy distinguishes treewidth from pathwidth
- (In)approximability of maximum minimal FVS
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Analyzing unit read-once refutations in difference constraint systems
- A relaxation of the directed disjoint paths problem: a global congestion metric helps
- Sparsification lower bound for linear spanners in directed graphs
- Mim-width. I. Induced path problems
- The complexity of finding temporal separators under waiting time constraints
- Spanning tree constrained determinantal point processes are hard to (approximately) evaluate
- Routing with congestion in acyclic digraphs
- Parameterized complexity of safe set
- Fixed parameter approximation scheme for min-max \(k\)-cut
- Fixed parameter approximation scheme for min-max \(k\)-cut
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
- On the maximum weight minimal separator
- Parameterized intractability of even set and shortest vector problem from Gap-ETH
- A tight lower bound for vertex planarization on graphs of bounded treewidth
- Structurally parameterized \(d\)-scattered set
- Reflections on kernelizing and computing unrooted agreement forests
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- Length-bounded cuts: proper interval graphs and structural parameters
- Parameterized complexity classes beyond para-NP
- New reduction rules for the tree bisection and reconnection distance
- The complexity of mixed-connectivity
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- On some FPT problems without polynomial Turing compressions
- Univariate ideal membership parameterized by rank, degree, and number of generators
- An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
- Parameterized multi-scenario single-machine scheduling problems
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
- Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs
- Refined parameterizations for computing colored cuts in edge-colored graphs
- On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan
- Parameterized complexity of independent set in \(H\)-free graphs
- On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
- Title not available (Why is that?)
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)
