Parameterized Algorithms
From MaRDI portal
Publication:5502162
DOI10.1007/978-3-319-21275-3zbMath1334.90001OpenAlexW2914414140WikidataQ56805475 ScholiaQ56805475MaRDI QIDQ5502162
Daniel Lokshtanov, Fedor V. Fomin, Michał Pilipczuk, Łukasz Kowalik, Dániel Marx, Marek Cygan, Marcin Pilipczuk, Saket Saurabh
Publication date: 17 August 2015
Full work available at URL: https://doi.org/10.1007/978-3-319-21275-3
treewidthmatroidslower boundskernelizationiterative compressionbounded search treescuts and separatorsdynamic programming on treewidthExponential-Time Hypothesisrandomized methods in parameterized algorithms
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Abstract computational complexity for mathematical programming problems (90C60) Dynamic programming (90C39) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) General applied mathematics (00A69) Mathematics for nonmathematicians (engineering, social sciences, etc.) (00A06) Mathematics in general (00A05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematics in general (00-01)
Related Items (only showing first 100 items - show all)
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 ⋮ On the proper orientation number of chordal graphs ⋮ On polynomial kernels for sparse integer linear programs ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ Compactors for parameterized counting problems ⋮ 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 + \epsilon ) k\)-vertex kernel for the dual coloring problem ⋮ Coloring problems on bipartite graphs of small diameter ⋮ On structural parameterizations of load coloring ⋮ Parameterized complexity of \(d\)-hitting set with quotas ⋮ The balanced satisfactory partition problem ⋮ Sorting by multi-cut rearrangements ⋮ Structural parameterizations of clique coloring ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Pattern matching in doubling spaces ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Cyclability in graph classes ⋮ A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ On exploring always-connected temporal graphs of small pathwidth ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Safe sets in graphs: graph classes and structural parameters ⋮ Finding disjoint paths on edge-colored graphs: more tractability results ⋮ Triangle-free planar graphs with small independence number ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Parameterizing edge modification problems above lower bounds ⋮ On the complexity of connection games ⋮ Treewidth distance on phylogenetic trees ⋮ Notes on complexity of packing coloring ⋮ \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments ⋮ Computational complexity of distance edge labeling ⋮ On the parameterized complexity of b-\textsc{chromatic number} ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ Reconfiguration on nowhere dense graph classes ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ The \(k\)-leaf spanning tree problem admits a klam value of 39 ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Parameterized complexity of superstring problems ⋮ Change-making problems revisited: a parameterized point of view ⋮ FPT approximation schemes for maximizing submodular functions ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ Structured proportional representation ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Exploiting hidden structure in selecting dimensions that distinguish vectors ⋮ Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis ⋮ Fixing improper colorings of graphs ⋮ Parameterized complexity of team formation in social networks ⋮ Corrigendum to: ``Advice classes of parameterized tractability ⋮ 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 ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Multi-attribute proportional representation ⋮ Edge bipartization faster than \(2^k\) ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ The minimum feasible tileset problem ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ On directed covering and domination problems ⋮ Co-clustering under the maximum norm ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ The complexity of dominating set in geometric intersection graphs ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Parameterized complexity of strip packing and minimum volume packing ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Partition on trees with supply and demand: kernelization and algorithms ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ Graph editing to a given degree sequence ⋮ On optimal approximability results for computing the strong metric dimension ⋮ \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions ⋮ The complexity of finding effectors ⋮ On the parameterized complexity of reconfiguration problems ⋮ On the complete width and edge clique cover problems ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ Complexity of secure sets ⋮ Stable matching games: manipulation via subgraph isomorphism ⋮ Fréchet distance between a line and avatar point set ⋮ Dynamic parameterized problems ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Approximability of clique transversal in perfect graphs ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Multi-budgeted directed cuts ⋮ The parameterised complexity of computing the maximum modularity of a graph ⋮ Best-case and worst-case sparsifiability of Boolean CSPs ⋮ Dual parameterization of weighted coloring ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Parameterized complexity of the anchored \(k\)-core problem for directed graphs
This page was built for publication: Parameterized Algorithms
