Fast FAST

DOI10.1007/978-3-642-02927-1_6zbMath1248.68547OpenAlexW2912532202MaRDI QIDQ3638023

Saket Saurabh, Noga Alon, Daniel Lokshtanov

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_6

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Parameterizing edge modification problems above lower bounds, Studies in Computational Aspects of Voting, What’s Next? Future Directions in Parameterized Complexity, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, Problems on finite automata and the exponential time hypothesis, Unnamed Item, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Kernel and fast algorithm for dense triplet inconsistency, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Effective computation of immersion obstructions for unions of graph classes, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number, A survey of parameterized algorithms and the complexity of edge modification, Confronting intractability via parameters, Kernels for feedback arc set in tournaments, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, Ranking and Drawing in Subexponential Time, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, Cluster editing: kernelization based on edge cuts, A quadratic vertex kernel for feedback arc set in bipartite tournaments, Slightly Superexponential Parameterized Problems, Fixed-parameter tractability results for feedback set problems in tournaments, Cluster editing with locally bounded modifications, Unnamed Item, Cluster Editing: Kernelization Based on Edge Cuts, A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs, A polynomial kernel for trivially perfect editing, On the threshold of intractability, A Subexponential Parameterized Algorithm for Proper Interval Completion, Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems, Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number, Packing Arc-Disjoint Cycles in Tournaments, On width measures and topological problems on semi-complete digraphs, Exploring the Subexponential Complexity of Completion Problems, Editing to Connected F-Degree Graph, Tournaments and Semicomplete Digraphs, Locally Semicomplete Digraphs and Generalizations, Tractability of König edge deletion problems, Unnamed Item, On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments