Parameterized graph separation problems

DOI10.1016/J.TCS.2005.10.007zbMATH Open1086.68104OpenAlexW2121641644MaRDI QIDQ820151FDOQ820151

Authors: Dániel Marx 

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

Recommendations

• Parameterized and Exact Computation
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
• Graph separators: A parameterized view
• On the parameterized complexity of finding separators with non-hereditary properties

zbMATH Keywords

parameterized complexitymulticutseparatormultiway cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Applications of a Planar Separator Theorem
• Finding good approximate vertex and edge partitions is NP-hard
• The Complexity of Multiterminal Cuts
• Multiway cuts in node weighted graphs
• Title not available (Why is that?)
• Finding and counting given length cycles
• A Separator Theorem for Planar Graphs
• Title not available (Why is that?)
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
• Title not available (Why is that?)
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Tight lower bounds for certain parameterized NP-hard problems
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• Balanced judicious bipartition is fixed-parameter tractable
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Designing FPT algorithms for cut problems using randomized contractions
• Faster algorithms for all-pairs bounded min-cuts
• FPT algorithms for path-transversal and cycle-transversal problems
• The vertex \(k\)-cut problem
• On polynomial kernels for structural parameterizations of odd cycle transversal
• Algorithms for Multiterminal Cuts
• Parameterized complexity of weighted multicut in trees
• Parameterized complexity of multicut in weighted trees
• What's next? Future directions in parameterized complexity
• Improved parameterized and exact algorithms for cut problems on trees
• Multi-budgeted directed cuts
• Multi-budgeted directed cuts
• Critical node detection problem for complex network in undirected weighted networks
• On the complexity of barrier resilience for fat regions and bounded ply
• Almost 2-SAT is fixed-parameter tractable
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• New abilities and limitations of spectral graph bisection
• A \(c^k n\) 5-approximation algorithm for treewidth
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Treewidth reduction for constrained separation and bipartization problems
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• Parameterized complexity of deletion to scattered graph classes
• Multicut in trees viewed through the eyes of vertex cover
• Restricted vertex multicut on permutation graphs
• Partitioning subclasses of chordal graphs with few deletions
• The maximum happy induced subgraph problem: bounds and algorithms
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• A faster parameterized algorithm for Group Feedback Edge Set
• Parameterizing cut sets in a graph by the number of their components
• Linear time parameterized algorithms for subset feedback vertex set
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• A survey of parameterized algorithms and the complexity of edge modification
• Graph-Based Representations in Pattern Recognition
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• Finding all leftmost separators of size \(\le k\)
• Linear kernels for separating a graph into components of bounded size
• Simple and improved parameterized algorithms for multiterminal cuts
• Title not available (Why is that?)
• Constant ratio fixed-parameter approximation of the edge multicut problem
• Subset feedback vertex set on graphs of bounded independent set size
• Subset feedback vertex set on graphs of bounded independent set size
• Parameterized and Exact Computation
• Solution methods for the vertex variant of the network system vulnerability analysis problem
• Important separators and parameterized algorithms
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• How to Cut a Graph into Many Pieces
• Multicut Is FPT
• On the parameterized complexity of computing balanced partitions in graphs
• On the parameterized complexity of finding separators with non-hereditary properties
• On the parameterized complexity of finding separators with non-hereditary properties
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• A note on triple separation of a graph
• Title not available (Why is that?)
• A logical approach to multicut problems
• An improved parameterized algorithm for the minimum node multiway cut problem
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• Some results on connected vertex separators
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Computation in causal graphs
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• The critical node detection problem in networks: a survey
• Minimum Bisection Is Fixed-Parameter Tractable
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
• Clique Cover and Graph Separation
• Parameterized complexity of critical node cuts
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Faster graph bipartization
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Parameterized algorithms for zero extension and metric labelling problems
• On the parameterized complexity of separating certain sources from the target
• Partitioning subclasses of chordal graphs with few deletions
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• Title not available (Why is that?)
• Clustering with Local Restrictions
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Finding \(k\)-secluded trees faster
• Finding \(k\)-secluded trees faster
• Quick separation in chordal and split graphs
• The \textsc{Red-Blue Separation} problem on graphs
• The firebreak problem
• On Weighted Graph Separation Problems and Flow Augmentation
• An approach to emulating separable graphs
• Approximating small balanced vertex separators in almost linear time
• \(\ell_p\)-norm multiway cut
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• Odd cycle transversal in mixed graphs
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Covering Vectors by Spaces: Regular Matroids
• Finding connected secluded subgraphs
• Deletion to scattered graph classes. I: Case of finite number of graph classes

This page was built for publication: Parameterized graph separation problems

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