scientific article; zbMATH DE number 6131596
From MaRDI portal
Publication:4904144
zbMath1258.68068MaRDI QIDQ4904144
Saket Saurabh, Dániel Marx, Daniel Lokshtanov
Publication date: 28 January 2013
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
A parameterized complexity view on collapsing \(k\)-cores, Efficiently approximating color-spanning balls, Algorithmic analysis of priority-based bin packing, Lower Bounds for the Graph Homomorphism Problem, On residual approximation in solution extension problems, On the optimality of exact and approximation algorithms for scheduling problems, On minimizing regular expressions without Kleene star, Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases, On the parameterised complexity of string morphism problems, Parameterized complexity and approximation issues for the colorful components problems, Complexity and approximation results on the shared transportation problem, Computational complexity of distance edge labeling, Known Algorithms for Edge Clique Cover are Probably Optimal, On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs, Strong partial clones and the time complexity of SAT problems, Counting Small Induced Subgraphs Satisfying Monotone Properties, The parameterised complexity of list problems on graphs of bounded treewidth, Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis, Finding optimal triangulations parameterized by edge clique cover, Problems on finite automata and the exponential time hypothesis, Unnamed Item, Learning from positive and negative examples: dichotomies and parameterized algorithms, A tight lower bound for vertex planarization on graphs of bounded treewidth, Finding a maximum minimal separator: graph classes and fixed-parameter tractability, Parameterized complexity of fair deletion problems, Hitting forbidden subgraphs in graphs of bounded treewidth, Linear kernels for outbranching problems in sparse digraphs, The parameterized complexity of local search for TSP, more refined, Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees, Covering problems for partial words and for indeterminate strings, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, A Dichotomy Result for Ramsey Quantifiers, Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations, Improved FPT algorithms for weighted independent set in bull-free graphs, Interval scheduling and colorful independent sets, Algorithms solving the matching cut problem, On the complexity of restoring corrupted colorings, Fixing improper colorings of graphs, Unnamed Item, A multistage view on 2-satisfiability, Sparsification and subexponential approximation, On the complexity of detecting hazards, On the \(d\)-claw vertex deletion problem, The P3 infection time is W[1-hard parameterized by the treewidth], Fractals for Kernelization Lower Bounds, Local search for string problems: brute-force is essentially optimal, Cliques enumeration and tree-like resolution proofs, Grundy Coloring and friends, half-graphs, bicliques, Complexity and lowers bounds for power edge set problem, Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments, Faster algorithms for vertex partitioning problems parameterized by clique-width, Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, Edge bipartization faster than \(2^k\), Complexity and inapproximability results for balanced connected subgraph problem, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, On feedback vertex set: new measure and new structures, Explicit linear kernels for packing problems, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, Dual parameterization of Weighted Coloring, Coloring invariants of knots and links are often intractable, Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms, Refining complexity analyses in planning by exploiting the exponential time hypothesis, Pattern matching and consensus problems on weighted sequences and profiles, A multi-parameter analysis of hard problems on deterministic finite automata, Temporal vertex cover with a sliding time window, Cluster editing with locally bounded modifications, Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms, Routing with congestion in acyclic digraphs, Unnamed Item, Complexity of token swapping and its variants, Complexity of independency and cliquy trees, The role of planarity in connectivity problems parameterized by treewidth, On the size of partial derivatives and the word membership problem, Metric dimension parameterized by treewidth, Unnamed Item, On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems, Hitting minors on bounded treewidth graphs. III. Lower bounds, Hitting forbidden induced subgraphs on bounded treewidth graphs, Fine-grained complexity of rainbow coloring and its variants, Concerning infeasibility of the wave functions of the universe, Minimum fill-in: inapproximability and almost tight lower bounds, Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms, Coloring Graphs with Constraints on Connectivity, Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs, Fine-Grained Complexity Theory (Tutorial), Problems on Finite Automata and the Exponential Time Hypothesis, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Defensive alliances in graphs, Subexponential parameterized algorithms for graphs of polynomial growth, Fine-Grained Complexity of Rainbow Coloring and its Variants., Dual parameterization of weighted coloring, Planar Digraphs, Fixed-parameter complexity and approximability of norm maximization, An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems, A complexity and approximation framework for the maximization scaffolding problem, Algorithms and almost tight results for 3-colorability of small diameter graphs, Characterization and complexity results on jumping finite automata, Inferring local transition functions of discrete dynamical systems from observations of system behavior, Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter, Quasipolynomiality of the Smallest Missing Induced Subgraph, A note on hardness of computing recursive teaching dimension, The 2CNF Boolean formula satisfiability problem and the linear space hypothesis, What Is Known About Vertex Cover Kernelization?, Unnamed Item, Subsequences in bounded ranges: matching and analysis problems, Priority-based bin packing with subset constraints, Characterizing polynomial Ramsey quantifiers, Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth, Strong triadic closure in cographs and graphs of low maximum degree, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, On the \(d\)-claw vertex deletion problem, Unnamed Item, Recognizing \(k\)-clique extendible orderings, Unnamed Item, Unnamed Item, Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem, Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
