scientific article; zbMATH DE number 7525479

DOI10.4230/LIPICS.ESA.2019.42MaRDI QIDQ5075784FDOQ5075784

Authors: Eduard Eiben, Daniel Lokshtanov, Amer E. Mouawad 

Publication date: 11 May 2022

Title of this publication is not available (Why is that?)

zbMATH Keywords

convolutiontreewidthbisectionhardness in Pfine-grained analysis

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations
• Clustered Integer 3SUM via Additive Combinatorics
• Title not available (Why is that?)
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Title not available (Why is that?)
• A polylogarithmic approximation of the minimum bisection
• A \(c^k n\) 5-approximation algorithm for treewidth
• On the parameterized complexity of computing graph bisections
• Partitioning Planar Graphs
• Subcubic equivalences between path, matrix, and triangle problems
• Minimum bisection is fixed parameter tractable
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• A parallel algorithm for bisection width in trees
• Approximating the minimum bisection size (extended abstract)
• Better approximations for tree sparsity in nearly-linear time
• On problems equivalent to \((\min,+)\)-convolution
• On some fine-grained questions in algorithms and complexity

Cited In (2)

• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth

This page was built for publication:

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