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)
- Parameterized complexity of conflict-free matchings and paths
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- 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
- Vertex partitioning problems on graphs with bounded tree width
- Finer tight bounds for coloring on clique-width
- Finer tight bounds for coloring on clique-width
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
- Title not available (Why is that?)
- Title not available (Why is that?)
- Paths to trees and cacti
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Parameterized approximation algorithms for bidirected Steiner network problems
- Parameterized algorithms for edge biclique and related problems
- On the relation of strong triadic closure and cluster deletion
- 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
- Title not available (Why is that?)
- 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}
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- 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
- 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
- Parameterized algorithms for queue layouts
- 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
- 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
- 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
- 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
- Exploiting \(c\)-closure in kernelization algorithms for graph problems
- The power of cut-based parameters for computing edge-disjoint paths
- Maximum minimal vertex cover parameterized by vertex cover
- On the number of labeled graphs of bounded treewidth
- Deleting vertices to graphs of bounded genus
- (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
- Parameterized complexity of perfectly matched sets
- 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
- On the maximum weight minimal separator
- A tight lower bound for vertex planarization on graphs of bounded treewidth
- Parameterized complexity classes beyond para-NP
- Structural parameterizations of Tracking Paths problem
- Some results on connected vertex separators
- Target set selection parameterized by vertex cover and more
- An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
- 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
- Finding temporal paths under waiting time constraints
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- The complexity of finding small separators in temporal graphs
- Parameterized Algorithms for Queue Layouts
- Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic Issues
- 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)
