Restricted vertex multicut on permutation graphs

DOI10.1016/j.dam.2012.03.021zbMath1246.05153OpenAlexW2088035239MaRDI QIDQ444445

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 algorithmsplit graphspermutation graphsmulticut problem

Mathematics Subject Classification ID

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

Related Items (4)

Parameterized complexity of multicut in weighted trees ⋮ The critical node detection problem in networks: a survey ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Quick separation in chordal and split graphs

Cites Work

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

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