SOFSEM 2006: Theory and Practice of Computer Science

DOI10.1007/11611257zbMATH Open1175.68294OpenAlexW2756057450MaRDI QIDQ5897992FDOQ5897992

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

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

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)

Cited In (15)

• Computer Science Logic
• Computing with multi-row gomory cuts
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Almost 2-SAT is fixed-parameter tractable
• Title not available (Why is that?)
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Simplex partitioning via exponential clocks and the multiway cut problem
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Parameterized complexity of length-bounded cuts and multicuts
• Performing Multicut on Walkable Environments
• Solution methods for the vertex variant of the network system vulnerability analysis problem
• Towards Algorithmic Cut-Introduction
• Multicut Is FPT
• A logical approach to multicut problems
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs

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)