Quick separation in chordal and split graphs

DOI10.4230/LIPICS.MFCS.2020.70OpenAlexW3082263377MaRDI QIDQ5089243FDOQ5089243

Saket Saurabh, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, 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

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

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)