Restricted vertex multicut on permutation graphs

DOI10.1016/J.DAM.2012.03.021MaRDI QIDQ444445zbMATHOpenAlexFDO

Authors Charis Papadopoulos

Publication date 14 August 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.03.021

zbMATH Keywords

NP-completenesspolynomial-time algorithmpermutation graphssplit graphsmulticut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 3919840
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• scientific article; zbMATH DE number 3900817

Cites work

• scientific article; zbMATH DE number 3876616 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3314878 (Why is no real title available?)
• A Characterisation of the Minimal Triangulations of Permutation Graphs
• Algorithmic graph theory and perfect graphs
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Constant ratio fixed-parameter approximation of the edge multicut problem
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Graph Classes: A Survey
• Minimal multicut and maximal integer multiflow: a survey
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Multiway cuts in node weighted graphs
• Parameterized graph separation problems
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The Complexity of Multiterminal Cuts
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth and minimum fill-in on permutation graphs in linear time
• \textsc{Multicut} is FPT

Cited in

(6)

• Quick separation in chordal and split graphs
• The critical node detection problem in networks: a survey
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• scientific article; zbMATH DE number 5519216 (Why is no real title available?)
• Parameterized complexity of multicut in weighted trees

This page was built for publication: Restricted vertex multicut on permutation graphs

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