Minimum separator reconfiguration

DOI10.4230/LIPICS.IPEC.2023.9MaRDI QIDQ6926201zbMATH OpenFDO

Authors Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinícius F. dos Santos, Tom C. van der Zanden

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.9

zbMATH Keywords

combinatorial reconfigurationkernelizationminimum separatorsparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• Approximability of partitioning graphs with supply and demand
• In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent
• Infeasibility of instance compression and succinct PCPs for NP
• Kernelization Lower Bounds by Cross-Composition
• New limits to classical and quantum instance compression
• On finding short reconfiguration sequences between independent sets
• On problems without polynomial kernels
• Parameterized algorithms
• Partitioning hypergraphs in scientific computing applications through vertex separators on graphs
• Reconfiguration graphs for dominating sets
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Shortest reconfiguration of perfect matchings via alternating cycles
• Straightening polygonal arcs and convexifying polygonal cycles
• Sublinear time width-bounded separators and their application to the protein side-chain packing problem
• Zur allgemeinen Kurventheorie.

Cited in

(1)

• Solution discovery via reconfiguration for problems in P

This page was built for publication: Minimum separator reconfiguration

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