Restricted vertex multicut on permutation graphs

DOI10.1016/J.DAM.2012.03.021zbMATH Open1246.05153OpenAlexW2088035239MaRDI QIDQ444445FDOQ444445

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

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

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)

Cites Work

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

Cited In (6)

• Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
• Parameterized complexity of multicut in weighted trees
• Title not available (Why is that?)
• Quick separation in chordal and split graphs
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• The critical node detection problem in networks: a survey

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)