scientific article; zbMATH DE number 7376039
From MaRDI portal
DOI10.4230/LIPIcs.ICALP.2018.112zbMath1499.68290arXiv2012.14174MaRDI QIDQ5002797
Mingyu Xiao, Hiroshi Nagamochi
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/2012.14174
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Parameterized graph separation problems
- Efficient algorithms for decomposing graphs under degree constraints
- Simple and improved parameterized algorithms for multiterminal cuts
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- An improved parameterized algorithm for the minimum node multiway cut problem
- A Polylogarithmic Approximation of the Minimum Bisection
- Finding small balanced separators
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Approximating the minimum bisection size (extended abstract)
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- Minimum bisection is fixed parameter tractable
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Expander flows, geometric embeddings and graph partitioning
