Quick separation in chordal and split graphs

DOI10.4230/LIPICS.MFCS.2020.70MaRDI QIDQ5089243zbMATH OpenOpenAlexFDO

Authors Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh, Roohani Sharma

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.MFCS.2020.70

zbMATH Keywords

kernelchordal graphsFPTmulticutmultiway cut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
• An improved parameterized algorithm for the minimum node multiway cut problem
• Clique Cover and Graph Separation
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Improved upper bounds for vertex cover
• Kernelization. Theory of parameterized preprocessing
• Multicut Is FPT
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Parameterized graph separation problems
• Restricted vertex multicut on permutation graphs
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• The Complexity of Multiterminal Cuts

Cited in

(3)

• On finding separators in temporal split and permutation graphs
• Fast diameter computation within split graphs
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage

This page was built for publication: Quick separation in chordal and split graphs

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