Parameterized algorithms
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
- On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
- Structural parameterizations of budgeted graph coloring
- On guarding orthogonal polygons with sliding cameras
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Communication complexity of pairs of graph families with applications
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Fixed-parameter tractability of \((n-k)\) list coloring
- 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
- Multi-attribute proportional representation
- A Parameterized Perspective on Attacking and Defending Elections
- On the tree augmentation problem
- Towards a polynomial kernel for directed feedback vertex set
- Towards a polynomial kernel for directed feedback vertex set
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- How hard is it to satisfy (almost) all roommates?
- On directed covering and domination problems
- Co-clustering under the maximum norm
- The complexity of dominating set in geometric intersection graphs
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- Parameterized algorithms and kernels for rainbow matching
- Deciding the existence of a cherry-picking sequence is hard on two trees
- On directed Steiner trees with multiple roots
- Orthogonal tree decompositions of graphs
- Parameterized Dynamic Cluster Editing
- Backdoors to planning
- \(k\)-distinct in- and out-branchings in digraphs
- Parameterized Complexity of Directed Spanner Problems.
- On 2-clubs in graph-based data clustering: theory and algorithm engineering
- Fast algorithms for parameterized problems with relaxed disjointness constraints
- The complexity landscape of decompositional parameters for ILP
- Swapping colored tokens on graphs
- An improved FPT algorithm for almost forest deletion problem
- Polynomial kernels for deletion to classes of acyclic digraphs
- FPT-algorithms for some problems related to integer programming
- Title not available (Why is that?)
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- Parameterized algorithms for queue layouts
- Approximation and hardness of shift-bribery
- Parameterized algorithms for book embedding problems
- Preference swaps for the stable matching problem
- Computing Tree Decompositions
- Parameterized complexity of directed Steiner tree on sparse graphs
- Parameterized complexity of directed spanner problems
- Parameterized complexity of secluded connectivity problems
- Problems on finite automata and the exponential time hypothesis
- Problems on finite automata and the exponential time hypothesis
- A parameterized perspective on protecting elections
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exploiting \(c\)-closure in kernelization algorithms for graph problems
- Reducing CMSO model checking to highly connected graphs
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Kernels for deletion to classes of acyclic digraphs
- Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
- The \(k\)-leaf spanning tree problem admits a klam value of 39
- \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
- On the complexity of and solutions to the minimum stopping and trapping set problems
- Parameterized complexity of perfectly matched sets
- Fixed parameter approximation scheme for min-max \(k\)-cut
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- Change-making problems revisited: a parameterized point of view
- Improving TSP tours using dynamic programming over tree decompositions
- The complexity of routing with collision avoidance
- The constant inapproximability of the parameterized dominating set problem
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- Small resolution proofs for QBF using dependency treewidth
- Finding geometric representations of apex graphs is \textsf{NP}-hard
- Dealing with several parameterized problems by random methods
- On the (parameterized) complexity of recognizing well-covered \((r,\ell)\)-graphs
- Structural parameterizations of Tracking Paths problem
- Some results on connected vertex separators
- Target set selection parameterized by vertex cover and more
- Parameterized complexity of fair vertex evaluation problems
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Parameterized algorithms for stable matching with ties and incomplete lists
- Solving problems on graphs of high rank-width
- Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
- Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization
- The graph motif problem parameterized by the structure of the input graph
- Parameterized complexity of independent set in \(H\)-free graphs
- On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Finding temporal paths under waiting time constraints
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
- Upper and lower degree-constrained graph orientation with minimum penalty
- 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
- Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
- Multivariate algorithmics for finding cohesive subnetworks
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)
