scientific article; zbMATH DE number 2234775

Publication date 1 December 2005

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

Mathematics Subject Classification ID

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

Recommendations

Parametrized complexity theory.
Parameterized algorithms
Fundamentals of parameterized complexity
Parameterized complexity: the main ideas and connections to practical computing
Mathematical Foundations of Computer Science 2004

Cited in

(only showing first 100 items - show all)

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
Eigenvalue location in graphs of small clique-width
Defensive alliances in graphs of bounded treewidth
Triangle-free planar graphs with small independence number
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
Change-making problems revisited: a parameterized point of view
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
Matchings with lower quotas: algorithms and complexity
Sparsification and subexponential approximation
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
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
Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
Parameterized computational complexity of finding small-diameter subgraphs
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
Augmenting tractable fragments of abstract argumentation
Parameterized complexity of machine scheduling: 15 open problems
On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
Reconstructing gene trees from Fitch's xenology relation
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
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 k for vertex cover
Capacitated domination faster than O(2ⁿ)
On the Grundy and b-chromatic numbers of a graph
On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
New fixed-parameter algorithms for the minimum quartet inconsistency problem
Towards a dichotomy for the possible winner problem in elections based on scoring rules
Betweenness parameterized above tight lower bound
Parameterized complexity and local search approaches for the stable marriage problem with ties
On the parameterized tractability of single machine scheduling with rejection
Paths to trees and cacti
On the parameterized complexity of contraction to generalization of trees
The complexity of finding small separators in temporal graphs
On the parameterized complexity of consensus clustering
On the hardness of maximum rank aggregation problems
Partial information network queries
A parameterized perspective on protecting elections
Measuring what matters: a hybrid approach to dynamic programming with treewidth
Complete-subgraph-transversal-sets problem on bounded treewidth graphs
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
The complexity of dependency detection and discovery in relational databases
On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
A balm: defend the clique-based attack from a fundamental aspect
Refined parameterizations for computing colored cuts in edge-colored graphs
On the complexity of approximately matching a string to a directed graph

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5710169)