SOFSEM 2006: Theory and Practice of Computer Science

DOI10.1007/11611257MaRDI QIDQ5897992zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, Johannes Uhlmann

Publication date 14 November 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11611257

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Algorithms for Multiterminal Cuts
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth

Cited in

(26)

• The complexity of multicut and mixed multicut problems in (di)graphs
• A parameterized algorithm for mixed-cut
• Computer Science Logic
• Computing with multi-row gomory cuts
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Multicut on graphs of bounded clique-width
• Almost 2-SAT is fixed-parameter tractable
• Parameterized complexity dichotomy for Steiner Multicut
• Solving multicut faster than \(2^{n }\)
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• An improved parameterized algorithm for the multicut problem
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• scientific article; zbMATH DE number 7378605 (Why is no real title available?)
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Simplex partitioning via exponential clocks and the multiway cut problem
• Restricted vertex multicut on permutation graphs
• Parameterized complexity of length-bounded cuts and multicuts
• Performing Multicut on Walkable Environments
• On the dominant of the multicut polytope
• Solution methods for the vertex variant of the network system vulnerability analysis problem
• Towards Algorithmic Cut-Introduction
• New results on planar and directed multicuts
• Multicut Is FPT
• A logical approach to multicut problems
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Faster exact algorithms for some terminal set problems

This page was built for publication: SOFSEM 2006: Theory and Practice of Computer Science

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