Restricted vertex multicut on permutation graphs
type: Item
instance of: scholarly article
title: Restricted vertex multicut on permutation graphs
zbMATH Open document ID: 1246.05153
author: Charis Papadopoulos
published in: Discrete Applied Mathematics
publication date: 2012-08-14T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6065741
zbMATH Keywords: multicut problem
zbMATH Keywords: permutation graphs
zbMATH Keywords: split graphs
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: NP-completeness
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2012.03.021
OpenAlex ID: W2088035239
cites work: Treewidth and Pathwidth of Permutation Graphs
cites work: Treewidth and Minimum Fill-in on d-Trapezoid Graphs
cites work: Multicut is FPT
cites work: Graph Classes: A Survey
cites work: Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
cites work: Minimal multicut and maximal integer multiflow: a survey
cites work: The Complexity of Multiterminal Cuts
cites work: Q4198056
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: Multiway cuts in node weighted graphs
cites work: Algorithmic graph theory and perfect graphs
cites work: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
cites work: Q5595961
cites work: Parameterized graph separation problems
cites work: Constant ratio fixed-parameter approximation of the edge multicut problem
cites work: Fixed-parameter tractability of multicut parameterized by the size of the cutset
cites work: A Characterisation of the Minimal Triangulations of Permutation Graphs
cites work: Treewidth and minimum fill-in on permutation graphs in linear time
cites work: Q3341921
DOI: 10.1016/J.DAM.2012.03.021
description: scientific article; zbMATH DE number 6065741