Parameterized graph separation problems
From MaRDI portal
Publication:820151
DOI10.1016/j.tcs.2005.10.007zbMath1086.68104OpenAlexW2121641644MaRDI QIDQ820151
Publication date: 6 April 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.007
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (only showing first 100 items - show all)
On the complexity of barrier resilience for fat regions and bounded ply ⋮ Faster exact algorithms for some terminal set problems ⋮ Linear kernels for separating a graph into components of bounded size ⋮ On Multiway Cut Parameterized above Lower Bounds ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ A logical approach to multicut problems ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ Finding all leftmost separators of size \(\le k\) ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ An improved parameterized algorithm for the minimum node multiway cut problem ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Critical node detection problem for complex network in undirected weighted networks ⋮ \(\ell_p\)-norm multiway cut ⋮ Clique Cover and Graph Separation ⋮ Odd cycle transversal in mixed graphs ⋮ Hitting Selected (Odd) Cycles ⋮ Finding connected secluded subgraphs ⋮ Finding \(k\)-secluded trees faster ⋮ Parameterized complexity of weighted multicut in trees ⋮ Some results on connected vertex separators ⋮ Parameterized complexity of multicut in weighted trees ⋮ The vertex \(k\)-cut problem ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ The firebreak problem ⋮ FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs ⋮ Algorithms for Multiterminal Cuts ⋮ Finding \(k\)-secluded trees faster ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multicut Is FPT ⋮ Unnamed Item ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Restricted vertex multicut on permutation graphs ⋮ Unnamed Item ⋮ Computation in Causal Graphs ⋮ FPT algorithms for path-transversal and cycle-transversal problems ⋮ A faster FPT algorithm for bipartite contraction ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Multi-Budgeted Directed Cuts ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ How to Cut a Graph into Many Pieces ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Clustering with Local Restrictions ⋮ The critical node detection problem in networks: a survey ⋮ Parameterized complexity of critical node cuts ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ List H-coloring a graph by removing few vertices ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The maximum happy induced subgraph problem: bounds and algorithms ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster graph bipartization ⋮ Approximating small balanced vertex separators in almost linear time ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Quick separation in chordal and split graphs ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ Almost 2-SAT is fixed-parameter tractable ⋮ Important Separators and Parameterized Algorithms ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ On the parameterized complexity of separating certain sources from the target ⋮ Multi-budgeted directed cuts ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time ⋮ Parameterized complexity of the anchored \(k\)-core problem for directed graphs ⋮ On group feedback vertex set parameterized by the size of the cutset ⋮ A survey of parameterized algorithms and the complexity of edge modification
Cites Work
- Finding and counting given length cycles
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Finding good approximate vertex and edge partitions is NP-hard
- Tight lower bounds for certain parameterized NP-hard problems
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- The Complexity of Multiterminal Cuts
- Multiway cuts in node weighted graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Parameterized graph separation problems
