scientific article; zbMATH DE number 2234775

Publication date: 1 December 2005

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

dynamic programming graph theory complexity of computation research exposition analysis of algorithms and problem complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Complexity and monotonicity results for domination games, On the ordered list subgraph embedding problems, An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification, Ranking chain sum orders, $(1, j)$-set problem in graphs, Win-win kernelization for degree sequence completion problems, A fast algorithm for permutation pattern matching based on alternating runs, Parameterized tractability of the maximum-duo preservation string mapping problem, Finding shortest paths between graph colourings, Graph isomorphism parameterized by elimination distance to bounded degree, The label cut problem with respect to path length and label frequency, Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control, On the hardness of bribery variants in voting with CP-nets, Rural postman parameterized by the number of components of required edges, On graphs with induced matching number almost equal to matching number, Algorithms for the workflow satisfiability problem engineered for counting constraints, $\mathrm{H}$-index manipulation by merging articles: models, theory, and experiments, Parameterized complexity of the $k$-arc Chinese postman problem, Prices matter for the parameterized complexity of shift bribery, Parameterized algorithms for the module motif problem, Refined algorithms for hitting many intervals, Parameterized complexity of $k$-anonymity: hardness and tractability, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, The parameterized complexity of local search for TSP, more refined, Increasing the minimum degree of a graph by contractions, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Parameterized complexity of Min-power multicast problems in wireless ad hoc networks, Finding approximate and constrained motifs in graphs, Incremental list coloring of graphs, parameterized by conservation, Two-layer planarization parameterized by feedback edge set, The complexity of the stamp folding problem, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Parameterized complexity of max-lifetime target coverage in wireless sensor networks, Maximum balanced subgraph problem parameterized above lower bound, Parameterized complexity of $k$-Chinese postman problem, Parameterized maximum path coloring, Parameterized complexity of MaxSat above average, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, The $l$-diversity problem: tractability and approximability, Polynomial kernels for proper interval completion and related problems, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, A new bound for 3-satisfiable MaxSat and its algorithmic application, Solving min ones 2-SAT as fast as vertex cover, Matching and weighted $P_2$-packing: algorithms and kernels, Revisiting the complexity of and/or graph solution, Parameterized complexity of connected even/odd subgraph problems, Effective computation of immersion obstructions for unions of graph classes, The constrained shortest common supersequence problem, Aspects of a multivariate complexity analysis for rectangle tiling, On the parameterized complexity of the repetition free longest common subsequence problem, Hardness of discrepancy computation and $\varepsilon$-net verification in high dimension, Parameterized complexity of finding small degree-constrained subgraphs, Finding kernels or solving SAT, Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, Editing graphs to satisfy degree constraints: a parameterized approach, On making directed graphs transitive, Graphs of separability at most 2, Parameterized complexity of generalized domination problems, A strengthened analysis of an algorithm for dominating set in planar graphs, Mod/Resc parsimony inference: theory and application, New results for the longest haplotype reconstruction problem, A note on the parameterized complexity of unordered maximum tree orientation, Parameterized Eulerian strong component arc deletion problem on tournaments, Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem, Local search: is brute-force avoidable?, Catalan structures and dynamic programming in $H$-minor-free graphs, Multicut in trees viewed through the eyes of vertex cover, On the parameterized complexity of coloring graphs in the absence of a linear forest, Parameterized proof complexity, Graph-based data clustering with overlaps, Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover, Stable assignment with couples: parameterized complexity and local search, Parameterized complexity and approximability of the longest compatible sequence problem, FPT algorithms for path-transversal and cycle-transversal problems, Paths of bounded length and their cuts: parameterized complexity and algorithms, On the directed full degree spanning tree problem, Lower bounds on kernelization, On the algorithmic effectiveness of digraph decompositions and complexity measures, The parameterized complexity of $k$-flip local search for SAT and MAX SAT, Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms, Subexponential parameterized algorithms, A survey of the algorithmic aspects of modular decomposition, Confronting intractability via parameters, Exploiting a hypergraph model for finding Golomb rulers, Parameterized complexity of three edge contraction problems with degree constraints, Practical algorithms for MSO model-checking on tree-decomposable graphs, Complexity of splits reconstruction for low-degree trees, Approximation algorithms for intersection graphs, Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Detecting monomials with $k$ distinct variables, A fixed-parameter algorithm for the vertex cover $P_3$ problem, Parametrized algorithms for random serial dictatorship, On the parameterized complexity of vertex cover and edge cover with connectivity constraints, Complexity of conflict-free colorings of graphs, Towards optimal and expressive kernelization for $d$-hitting set, Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy, Graphs with few $P_4$'s under the convexity of paths of order three, On the parameterized complexity of computing balanced partitions in graphs, Parameterizations of test cover with bounded test sizes, Parameterized algorithms for finding square roots, Increasing the Minimum Degree of a Graph by Contractions, Improved Parameterized Algorithms for above Average Constraint Satisfaction, Simpler Linear-Time Kernelization for Planar Dominating Set, Parameterized Maximum Path Coloring, The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability, Are there any nicely structured preference profiles nearby?, Parameterized complexity of the induced subgraph problem in directed graphs, The Birth and Early Years of Parameterized Complexity, The Impact of Parameterized Complexity to Interdisciplinary Problem Solving, A Basic Parameterized Complexity Primer, Kernelization – Preprocessing with a Guarantee, Parameterized Complexity and Subexponential-Time Computability, Graph Minors and Parameterized Algorithm Design, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Studies in Computational Aspects of Voting, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, What’s Next? Future Directions in Parameterized Complexity, Finding disjoint dense clubs in a social network, On the kernelization of split graph problems, Complexity results for rainbow matchings, Satisfying more than half of a system of linear equations over GF(2): a multivariate approach, Genus characterizes the complexity of certain graph problems: Some tight results, The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders, The parameterized complexity of unique coverage and its variants, Computing optimal Steiner trees in polynomial space, Parameterized complexity classes beyond para-NP, Paradigms for parameterized enumeration, Parameterized complexity of the MinCCA problem on graphs of bounded decomposability, On approximability of optimization problems related to red/blue-split graphs, A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack, Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs, A polynomial-time algorithm for outerplanar diameter improvement, Parameterized and exact algorithms for class domination coloring, Linear kernels for $k$-tuple and liar's domination in bounded genus graphs, The graph motif problem parameterized by the structure of the input graph, On the complexity of various parameterizations of common induced subgraph isomorphism, The complexity of degree anonymization by graph contractions, On the complexity of multi-parameterized cluster editing, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, On kernelization and approximation for the vector connectivity problem, Fixed-parameter tractable distances to sparse graph classes, Computing the flip distance between triangulations, Parameterized complexity dichotomy for $(r, \ell)$-\textsc{Vertex Deletion}, On the vertex cover $P_3$ problem parameterized by treewidth, Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?, Gerrymandering on graphs: computational complexity and parameterized algorithms, Parameterized edge Hamiltonicity, Metric Dimension of Bounded Width Graphs, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case, Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work, Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives, $p$-edge/vertex-connected vertex cover: parameterized and approximation algorithms, On the parameterized complexity of the Maximum Exposure Problem, Solving projected model counting by utilizing treewidth and its limits, Fair and efficient allocation with few agent types, few item types, or small value levels, Parameterized complexity of envy-free resource allocation in social networks, The parameterized complexity of stabbing rectangles, Approximation and tidying -- a problem kernel for $s$-plex cluster vertex deletion, Obtaining a planar graph by vertex deletion, Polynomial kernelizations for MIN $F^{+}\Pi _{1}$ and MAX NP, Sharp separation and applications to exact and parameterized algorithms, Tractable cases of the extended global cardinality constraint, The effect of homogeneity on the computational complexity of combinatorial data anonymization, Radiation hybrid map construction problem parameterized, Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey, Group activity selection with few agent types, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, Parameterized domination in circle graphs, A cubic-vertex kernel for flip consensus tree, The complexity of register allocation, Gene tree correction for reconciliation and species tree inference: complexity and algorithms, Imbalance is fixed parameter tractable, Testing consistency of quartet topologies: a parameterized approach, The parametric complexity of graph diameter augmentation, Towards optimal kernel for edge-disjoint triangle packing, On the $k$-edge-incident subgraph problem and its variants, Faster algorithms for vertex partitioning problems parameterized by clique-width, An improved parameterized algorithm for the independent feedback vertex set problem, Parameterized algorithms for load coloring problem, Rationalizations of Condorcet-consistent rules via distances of Hamming type, A linear kernel for the complementary maximal strip recovery problem, Searching for better fill-in, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, Solving \#SAT using vertex covers, Hitting Forbidden Minors: Approximation and Kernelization, Fixed-parameter algorithms for scaffold filling, The complexity of fully proportional representation for single-crossing electorates, Large Independent Sets in Subquartic Planar Graphs, Hybridization Number on Three Rooted Binary Trees is EPT, Faster Computation of Path-Width, On the Complexity of Computing the k-restricted Edge-connectivity of a Graph, Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs, Parameterized Complexity of Team Formation in Social Networks, On Generating Triangle-Free Graphs, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, Parameterized computation and complexity: a new approach dealing with NP-hardness, Parameterized Complexity of Control and Bribery for d-Approval Elections, The Multi-parameterized Cluster Editing Problem, Myhill-Nerode Methods for Hypergraphs, Chordless paths through three vertices, Parameterized graph separation problems, Parameterized coloring problems on chordal graphs, New algorithms for minimizing the weighted number of tardy jobs on a single machine, On the parameterized complexity of maximum degree contraction problem, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Isolation concepts for efficiently enumerating dense subgraphs, Data reductions, fixed parameter tractability, and random weighted $d$-CNF satisfiability, Constraint satisfaction with bounded treewidth revisited, FPT algorithms and kernels for the directed $k$-leaf problem, Fixed-parameter tractability of anonymizing data by suppressing entries, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Exact algorithms and applications for tree-like Weighted Set Cover, Polynomial kernels for 3-leaf power graph modification problems, Separator-based data reduction for signed graph balancing, A new upper bound for Max-2-SAT: A graph-theoretic approach, Interval scheduling and colorful independent sets, Infeasibility of instance compression and succinct PCPs for NP, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, Improved parameterized and exact algorithms for cut problems on trees, Algorithms solving the matching cut problem, The complexity of degree anonymization by vertex addition, Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules, Exploiting hidden structure in selecting dimensions that distinguish vectors, On the complexity of some colorful problems parameterized by treewidth, Computing bond orders in molecule graphs, A probabilistic approach to problems parameterized above or below tight bounds, Vertex cover problem parameterized above and below tight bounds, An FPT algorithm for the vertex cover $P_4$ problem, Breaking the $2^{n}$-barrier for irredundance: two lines of attack, Contracting planar graphs to contractions of triangulations, Hardness of subgraph and supergraph problems in $c$-tournaments, Quadratic kernelization for convex recoloring of trees, Solving MAX-$r$-SAT above a tight lower bound, Dominating set is fixed parameter tractable in claw-free graphs, Bandwidth on AT-free graphs, The complexity of König subgraph problems and above-guarantee vertex cover, Editing graphs into disjoint unions of dense clusters, Exact algorithms for the bottleneck Steiner tree problem, A new algorithm for finding trees with many leaves, Faster parameterized algorithms for \textsc{Minimum Fill-in}, An exact algorithm for the maximum leaf spanning tree problem, Parameterizing cut sets in a graph by the number of their components, Parameterized complexity of control problems in Maximin election, Note on Max Lin-2 above average, Spanners in sparse graphs, A generalization of Nemhauser and Trotter's local optimization theorem, Implicit branching and parameterized partial cover problems, Efficient algorithms for counting parameterized list $H$-colorings, Minimizing Rosenthal potential in multicast games, Restricted and swap common superstring: a multivariate algorithmic perspective, Augmenting graphs to minimize the diameter, Parameterized complexity analysis for the closest string with wildcards problem, 1.5D terrain guarding problem parameterized by guard range, On the complexity of computing the $k$-restricted edge-connectivity of a graph, Partition on trees with supply and demand: kernelization and algorithms, Fixed-parameter algorithms for DAG partitioning, On the parameterized complexity of the edge monitoring problem, Campaign management under approval-driven voting rules, A linear kernel for planar red-blue dominating set, The complexity of finding effectors, Algorithm engineering for color-coding with applications to signaling pathway detection, Fixed-parameter complexity of minimum profile problems, Improved algorithms and complexity results for power domination in graphs, Short cycles make $W$-hard problems hard: FPT algorithms for $W$-hard problems in graphs with no short cycles, Graph editing problems with extended regularity constraints, List H-coloring a graph by removing few vertices, On the parameterized complexity of reconfiguration problems, Algorithms for $k$-internal out-branching and $k$-tree in bounded degree graphs, On parameterized independent feedback vertex set, Sex-equal stable matchings: complexity and exact algorithms, On making a distinguished vertex of minimum degree by vertex deletion, Fixed-parameter tractability of satisfying beyond the number of variables, Parameterizing by the number of numbers, Complexity issues in vertex-colored graph pattern matching, Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring, A kernel of order $2k - c$ for Vertex Cover, Exact algorithms for cluster editing: Evaluation and experiments, FPT algorithms for connected feedback vertex set, Lower bounds for kernelizations and other preprocessing procedures, Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms, Minimum vertex cover in rectangle graphs, Cluster editing with locally bounded modifications, On families of categorial grammars of bounded value, their learnability and related complexity questions, Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover, Computing vertex-surjective homomorphisms to partially reflexive trees, Average parameterization and partial kernelization for computing medians, Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems, Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections, Complexity of secure sets, The parameterized complexity of $k$-edge induced subgraphs, Combinatorial filter reduction: special cases, approximation, and fixed-parameter tractability, Editing to a planar graph of given degrees, The complexity ecology of parameters: An illustration using bounded max leaf number, A single-exponential FPT algorithm for the $K_4$-\textsc{minor cover} problem, On the treewidth of dynamic graphs, An improved kernel size for rotation distance in binary trees, Faster approximation schemes and parameterized algorithms on (odd-)$H$-minor-free graphs, On bounded-degree vertex deletion parameterized by treewidth, Containment relations in split graphs, Possible winner problems on partial tournaments: a parameterized study, Augmenting weighted graphs to establish directed point-to-point connectivity, A general scheme for solving a large set of scheduling problems with rejection in FPT time, Sequential vector packing, On the fixed-parameter tractability of the equivalence test of monotone normal forms, Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG, Constrained stable marriage with free edges or few blocking pairs, From the $W$-hierarchy to XNLP. Classes of fixed parameter intractability, Finding geometric representations of apex graphs is NP-hard, Parameterized complexity of reconfiguration of atoms, Parameterized complexity of immunization in the threshold model, A parameterized view to the robust recoverable base problem of matroids under structural uncertainty, Distance from triviality 2.0: hybrid parameterizations, Parameterized analysis and crossing minimization problems, Sparse obstructions for minor-covering parameters, Color spanning objects: algorithms and hardness results, Parameterized complexity of conflict-free matchings and paths, Parameterized multi-scenario single-machine scheduling problems, Betweenness parameterized above tight lower bound, Parameterized complexity and local search approaches for the stable marriage problem with ties, The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be?, Parameterized dynamic cluster editing, On structural parameterizations of the bounded-degree vertex deletion problem, New width parameters for SAT and \#SAT, The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints, On the parameterized tractability of single machine scheduling with rejection, Detecting fixed patterns in chordal graphs in polynomial time, Parameterized approximability of maximizing the spread of influence in networks, Paths to trees and cacti, On the parameterized complexity of contraction to generalization of trees, Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, Constant thresholds can make target set selection tractable, Control complexity in Bucklin and fallback voting: a theoretical analysis, A multi-parameter analysis of hard problems on deterministic finite automata, On explaining integer vectors by few homogeneous segments, Minimum fill-in of sparse graphs: kernelization and approximation, Colored hypergraph isomorphism is fixed parameter tractable, The complexity of finding small separators in temporal graphs, Algorithms for propositional model counting, Fixed-parameter tractability results for feedback set problems in tournaments, Parameterized computational complexity of Dodgson and Young elections, On the parameterized complexity of consensus clustering, Pursuing a fast robber on a graph, Clustering with partial information, Optimization for first order Delaunay triangulations, On the hardness of maximum rank aggregation problems, Partial information network queries, Applying modular decomposition to parameterized cluster editing problems, Parameterized complexity of a coupled-task scheduling problem, A parameterized perspective on protecting elections, Measuring what matters: a hybrid approach to dynamic programming with treewidth, On the parameterized tractability of the just-in-time flow-shop scheduling problem, Complete-subgraph-transversal-sets problem on bounded treewidth graphs, On the parameterized complexity of graph modification to first-order logic properties, Fine-grained complexity of rainbow coloring and its variants, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, Optimal tree decompositions revisited: a simpler linear-time FPT algorithm, The complexity of finding temporal separators under waiting time constraints, Dividing splittable goods evenly and with limited fragmentation, The complexity of dependency detection and discovery in relational databases, An improved linear kernel for complementary maximal strip recovery: simpler and smaller, Backdoors to planning, The parameterized complexity of the minimum shared edges problem, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?, On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem, Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: a review, A balm: defend the clique-based attack from a fundamental aspect, Refined parameterizations for computing colored cuts in edge-colored graphs, Using contracted solution graphs for solving reconfiguration problems, On the parameterized complexity of separating certain sources from the target, On the complexity of approximately matching a string to a directed graph, Introduction to reconfiguration, Colored cut games, Revising Johnson's table for the 21st century, On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates, A polynomial kernel for bipartite permutation vertex deletion, Moderate exponential-time algorithms for scheduling problems, The complexity of finding harmless individuals in social networks, Eternal vertex cover on bipartite graphs, Fixed-parameter complexity and approximability of norm maximization, On structural parameterizations for the 2-club problem, Methods for solving reasoning problems in abstract argumentation -- a survey, Backdoors to tractable answer set programming, Pure Nash equilibria in graphical games and treewidth, Parameterizations of hitting set of bundles and inverse scope, Finding disjoint paths in networks with star shared risk link groups, On the kernelization of ranking $r$-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments, Capacitated domination: problem complexity and approximation algorithms, Combinatorial voter control in elections, Using patterns to form homogeneous teams, A refined complexity analysis of degree anonymization in graphs, Maximum induced matchings close to maximum matchings, Approximability and parameterized complexity of multicover by $c$-intervals, Fine-grained parameterized complexity analysis of graph coloring problems, Editing to a graph of given degrees, Some results on more flexible versions of Graph Motif, An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems, Parameterized complexity of control and bribery for $d$-approval elections, A fixed-parameter algorithm for guarding 1.5D terrains, Inferring local transition functions of discrete dynamical systems from observations of system behavior, Eigenvalue location in graphs of small clique-width, Defensive alliances in graphs of bounded treewidth, Triangle-free planar graphs with small independence number, Parameterizing edge modification problems above lower bounds, On the complexity of rainbow coloring problems, The $S$-\textsc{labeling} problem: an algorithmic tour, The complexity of probabilistic lobbying, Exact and heuristic algorithms for thrift cyclic scheduling, Note on maximal bisection above tight lower bound, Calculating approximation guarantees for partial set cover of pairs, Parameterized complexity of superstring problems, Change-making problems revisited: a parameterized point of view, FPT approximation schemes for maximizing submodular functions, Exact combinatorial algorithms and experiments for finding maximum $k$-plexes, A new view on rural postman based on Eulerian extension and matching, Improved Steiner tree algorithms for bounded treewidth, A golden ratio parameterized algorithm for cluster editing, Improved FPT algorithms for weighted independent set in bull-free graphs, Bivariate complexity analysis of \textsc{Almost Forest Deletion}, Structured proportional representation, Parameterized approximation via fidelity preserving transformations, Sublinear approximation algorithms for boxicity and related problems, Spanners of bounded degree graphs, Even faster parameterized cluster deletion and cluster editing, Subexponential algorithms for partial cover problems, A kernel of order $2k-c\log k$ for vertex cover, Capacitated domination faster than $O(2^n)$, Matchings with lower quotas: algorithms and complexity, Sparsification and subexponential approximation, On the Grundy and $b$-chromatic numbers of a graph, On the (non-)existence of polynomial kernels for $P _{l }$-free edge modification problems, Parameterized complexity of team formation in social networks, Solving problems on graphs of high rank-width, Parameterized complexity of theory of mind reasoning in dynamic epistemic logic, New fixed-parameter algorithms for the minimum quartet inconsistency problem, Towards a dichotomy for the possible winner problem in elections based on scoring rules, Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments, Multi-attribute proportional representation, Maximum disjoint paths on edge-colored graphs: approximability and tractability, Pattern-guided $k$-anonymity, The parameterized complexity of the rainbow subgraph problem, Finding supported paths in heterogeneous networks, Co-clustering under the maximum norm, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, FPT algorithms for domination in sparse graphs and beyond, The complexity of routing with collision avoidance, The complexity landscape of decompositional parameters for ILP, On the complexity of wafer-to-wafer integration, An improved FPT algorithm for almost forest deletion problem, Complexity of Grundy coloring and its variants, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, Parameterized complexity of asynchronous border minimization, The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs, Parameterized computational complexity of finding small-diameter subgraphs, On the fixed-parameter tractability of parameterized model-checking problems, Two fixed-parameter algorithms for vertex covering by paths on trees, Treewidth computations. I: Upper bounds, Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming, Multivariate complexity analysis of Swap Bribery, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion, Parameterized measure \& conquer for problems with no small kernels, A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications, Augmenting tractable fragments of abstract argumentation, A cubic kernel for feedback vertex set and loop cutset, W-hierarchies defined by symmetric gates, Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Homogeneous string segmentation using trees and weighted independent sets, Parameterized approximation of dominating set problems, Reconstructing $hv$-convex multi-coloured polyominoes, Simple and improved parameterized algorithms for multiterminal cuts, Fixed-parameter algorithms for cluster vertex deletion, Parameterized complexity of machine scheduling: 15 open problems, Linear kernelizations for restricted 3-Hitting Set problems, On the (parameterized) complexity of recognizing well-covered ($r$,$\ell$)-graph, Constant ratio fixed-parameter approximation of the edge multicut problem, Reconstructing gene trees from Fitch's xenology relation, A fixed parameter algorithm for optimal convex partitions, Closest 4-leaf power is fixed-parameter tractable, Parameterizing above or below guaranteed values, The minimum spanning strong subdigraph problem is fixed parameter tractable, A more effective linear kernelization for cluster editing, Learning large-alphabet and analog circuits with value injection queries, Red-blue covering problems and the consecutive ones property, On parameterized complexity of the multi-MCS problem, Covering graphs with few complete bipartite subgraphs, Algorithms for compact letter displays: comparison and evaluation, Parameterized complexity of finding regular induced subgraphs, The parameterized complexity of the induced matching problem, Parameterized computational complexity of control problems in voting systems, Almost 2-SAT is fixed-parameter tractable, Fixed-parameter algorithms for Kemeny rankings, Minimum leaf out-branching and related problems, Isolation concepts for clique enumeration: comparison and computational experiments, Parameterized complexity of candidate control in elections and related digraph problems, Going weighted: parameterized algorithms for cluster editing, Backdoor sets of quantified Boolean formulas, Multiple hypernode hitting sets and smallest two-cores with targets, The union of minimal hitting sets: parameterized combinatorial bounds and counting, A fixed-parameter tractability result for multicommodity demand flow in trees, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams, Solving Problems on Graphs of High Rank-Width, Kernelization of Cycle Packing with Relaxed Disjointness Constraints, Consensus Patterns (Probably) Has no EPTAS, Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints, On the Equivalence among Problems of Bounded Width, Unnamed Item, Parameterized Power Vertex Cover, A Faster Parameterized Algorithm for Group Feedback Edge Set, Choosability of P 5-Free Graphs, On Making Directed Graphs Transitive, A Polynomial-Time Algorithm for Outerplanar Diameter Improvement, Editing to a Planar Graph of Given Degrees, Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets, Bivariate Complexity Analysis of Almost Forest Deletion, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths, On the Complexity of Wafer-to-Wafer Integration, Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints, Algorithms Solving the Matching Cut Problem, Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems, Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree, Privacy in Elections: k-Anonymizing Preference Orders, Algorithms for Propositional Model Counting, Improved Algorithms for Bicluster Editing, Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems, Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms], A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors, Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters, An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees, New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem, Capacitated Domination and Covering: A Parameterized Perspective, Parameterized Complexity and Approximability of the SLCS Problem, A Linear Kernel for Planar Feedback Vertex Set, Exact Algorithms for Cluster Editing: Evaluation and Experiments, Parameterized Algorithms and Hardness Results for Some Graph Motif Problems, On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs, The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants, Segmenting Strings Homogeneously Via Trees, Fixed-Parameter Algorithms for Kemeny Scores, Minimum Leaf Out-Branching Problems, Parameterized Computational Complexity of Dodgson and Young Elections, Multicut Is FPT, Parameterized and Exact Algorithms for Class Domination Coloring, Fractals for Kernelization Lower Bounds, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, On the Computational Complexity of Variants of Combinatorial Voter Control in Elections, The Alcuin Number of a Graph, Faster Steiner Tree Computation in Polynomial-Space, Genomic Scaffold Filling: A Progress Report, Finding Disjoint Dense Clubs in an Undirected Graph, A 42k Kernel for the Complementary Maximal Strip Recovery Problem, Parameterized Complexity of k-Anonymity: Hardness and Tractability, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, An Experimental Study on Generating Planar Graphs, Finding Approximate and Constrained Motifs in Graphs, A Problem Kernelization for Graph Packing, Clustering with Partial Information, Monadic Second Order Logic on Graphs with Local Cardinality Constraints, Fixed-parameter tractability results for full-degree spanning tree and its dual, Kernelization and complexity results for connectivity augmentation problems, Efficient Algorithms for Eulerian Extension, Milling a Graph with Turn Costs: A Parameterized Complexity Perspective, A Quartic Kernel for Pathwidth-One Vertex Deletion, On the Kernelization Complexity of Colorful Motifs, Partial Kernelization for Rank Aggregation: Theory and Experiments, Cluster Editing: Kernelization Based on Edge Cuts, Computing the Deficiency of Housing Markets with Duplicate Houses, Multivariate Complexity Analysis of Swap Bribery, On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems, On the Grundy Number of a Graph, Parameterized Complexity of Stabbing Rectangles and Squares in the Plane, On Making a Distinguished Vertex Minimum Degree by Vertex Deletion, Structural Properties of Hard Metric TSP Inputs, O(1)-Approximations for Maximum Movement Problems, The Effect of Homogeneity on the Complexity of k-Anonymity, A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application, Polynomial Kernels for Proper Interval Completion and Related Problems, Bidimensionality and Kernels, Deconstructing Intractability: A Case Study for Interval Constrained Coloring, Iterative Compression for Exactly Solving NP-Hard Minimization Problems, A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing, The Budgeted Unique Coverage Problem and Color-Coding, Important Separators and Parameterized Algorithms, List Coloring in the Absence of a Linear Forest, Planar k-Path in Subexponential Time and Polynomial Space, From Few Components to an Eulerian Graph by Adding Arcs, A Polynomial Time Algorithm for Bounded Directed Pathwidth, Kernelization: New Upper and Lower Bound Techniques, Planar Capacitated Dominating Set Is W[1-Hard], On Finding Directed Trees with Many Leaves, Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms, Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover, Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs, A Probabilistic Approach to Problems Parameterized above or below Tight Bounds, Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor, On the Directed Degree-Preserving Spanning Tree Problem, Polynomial Kernel for Interval Vertex Deletion, On the complexity of coloring ‐graphs, Equitable scheduling on a single machine, A state-of-the-art survey on multi-scenario scheduling, Parameterized complexity for iterated type partitions and modular-width, A multivariate complexity analysis of the material consumption scheduling problem, Maximum weight t-sparse set problem on vector-weighted graphs, On the Parameterized Approximability of Contraction to Classes of Chordal Graphs, Backdoors to Normality for Disjunctive Logic Programs, Iterated Type Partitions, Parameterized Analysis of Art Gallery and Terrain Guarding, As Time Goes By: Reflections on Treewidth for Temporal Graphs, A Retrospective on (Meta) Kernelization, Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Improved Upper Bounds for Partial Vertex Cover, Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms, On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Unnamed Item, Unnamed Item, Sum-of-Products with Default Values: Algorithms and Complexity Results, Determination of Glycan Structure from Tandem Mass Spectra, Computing Bond Types in Molecule Graphs, Graph-Based Data Clustering with Overlaps, Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments, Hitting Selected (Odd) Cycles, Parameterized complexity of perfectly matched sets, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, On the complexity of the cable-trench problem, Unnamed Item, Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules, Hedonic diversity games: a complexity picture with more than two colors, Parameterized algorithms and data reduction for the short secluded s‐t‐path problem, Immunization in the threshold model: a parameterized complexity study, Parameterized (Approximate) Defective Coloring, Disentangling the computational complexity of network untangling, CSP beyond tractable constraint languages, Solving infinite-domain CSPs using the patchwork property, On the Parameterized Complexity of Counting Small-Sized Minimum $\boldsymbol{(S,T)}$-Cuts, A survey of parameterized algorithms and the complexity of edge modification, A new perspective on single-machine scheduling problems with late work related criteria, Colorful graph coloring, More effort towards multiagent knapsack, Locating Eigenvalues of Symmetric Matrices - A Survey, Unnamed Item, Unnamed Item, Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs, Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs, The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number, The Parameterized Complexity of the Unique Coverage Problem, Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs, The Constant Inapproximability of the Parameterized Dominating Set Problem, Computing $k$-Atomicity in Polynomial Time, Monitoring the edges of a graph using distances, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Tractable answer-set programming with weight constraints: bounded treewidth is not enough, Robustness among multiwinner voting rules, A Practical Approach to Courcelle's Theorem, Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation), Slightly Superexponential Parameterized Problems, Induced Disjoint Paths in Claw-Free Graphs, Unnamed Item, Temporal graph classes: a view through temporal separators, Unnamed Item, Unnamed Item, Parameterized approximation algorithms for some location problems in graphs, Default logic and bounded treewidth, Parameterized algorithms for module map problems, Enumeration and maximum number of maximal irredundant sets for chordal graphs, Parameterized certificate dispersal and its variants, Finding large degree-anonymous subgraphs is hard, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, On the complexity of finding internally vertex-disjoint long directed paths, Large Independent Sets in Triangle-Free Planar Graphs, NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs, Your rugby mates don't need to know your colleagues: triadic closure with edge colors, On the complexity of finding large odd induced subgraphs and odd colorings, Fixed-Parameter Algorithms for Cluster Vertex Deletion, Better Algorithms and Bounds for Directed Maximum Leaf Problems, Covering Graphs with Few Complete Bipartite Subgraphs, Faster Existential FO Model Checking on Posets, Parameterized algorithms for finding highly connected solution, On finding separators in temporal split and permutation graphs, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, Incremental optimization of independent sets under the reconfiguration framework, The complexity of tree partitioning, On finding separators in temporal split and permutation graphs, Structural parameterizations of budgeted graph coloring, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), On the Parameterized Complexity of Contraction to Generalization of Trees., Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Dynamic programming for graphs on surfaces, Unnamed Item, Unnamed Item, Going Weighted: Parameterized Algorithms for Cluster Editing, Parameterized Graph Editing with Chosen Vertex Degrees, Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries, Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets, Parameterized Algorithms for Generalized Domination, On Computing the Maximum Parsimony Score of a Phylogenetic Network, Network-Based Vertex Dissolution, Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Parameterized algorithms for finding highly connected solution, Dividing splittable goods evenly and with limited fragmentation