scientific article
From MaRDI portal
Publication:2843923
zbMath1270.68112MaRDI QIDQ2843923
Elena Prieto, Michael R. Fellows, Frances A. Rosamond, Rodney G. Downey, Vladimir Estivill-Castro
Publication date: 27 August 2013
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S1571066104810144
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)
Related Items (38)
On miniaturized problems in parameterized complexity theory ⋮ Parameterized graph separation problems ⋮ Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Collaborating with Hans: Some Remaining Wonderments ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Forming \(k\) coalitions and facilitating relationships in social networks ⋮ Parameterized algorithms for graph partitioning problems ⋮ Clique Cover and Graph Separation ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ FPT approximation and subexponential algorithms for covering few or many edges ⋮ Parameterized random complexity ⋮ Confronting intractability via parameters ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ On the sum-max graph partitioning problem ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ On the computational hardness based on linear fpt-reductions ⋮ Unnamed Item ⋮ Computing minimum multiway cuts in hypergraphs ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Efficient algorithms for network localization using cores of underlying graphs ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ On problems without polynomial kernels ⋮ Univariate ideal membership parameterized by rank, degree, and number of generators ⋮ Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs ⋮ On the parameterized complexity of separating certain sources from the target ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
This page was built for publication:
