On the Parameterized Complexity of Computing Graph Bisections

No abstract is available for this paper.

• Publication year

  2013

• Venue

  International Workshop on Graph-Theoretic Concepts in Computer Science

• Publication date

  2013-06-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-45043-3_8
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms

  2012cited by this paper
• Balanced Partitions of Trees and Applications

  2012cited by this paper
• Applied Parallel Computing

  2012cited by this paper
• Customizable Route Planning

  2011cited by this paper
• Fast balanced partitioning is hard even on grids and trees

  2011influential reference
• Finding small separators in linear time via treewidth reduction

  2011cited by this paper
• Algorithms – ESA 2011

  2011cited by this paper
• An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs

  2011cited by this paper
• Improved upper bounds for vertex cover

  2010cited by this paper
• Cross-Composition: A New Technique for Kernelization Lower Bounds

  2010cited by this paper
• Kernelization: New Upper and Lower Bound Techniques

  2009cited by this paper
• Treewidth Reduction for Constrained Separation and Bipartization Problems

  2009cited by this paper
• Optimal hierarchical decompositions for congestion minimization in networks

  2008cited by this paper
• Width Parameters Beyond Tree-width and their Applications

  2008cited by this paper
• Invitation to data reduction and problem kernelization

  2007cited by this paper
• Multi-level mu -Finite Element Analysis for Human Bone Structures

  2006cited by this paper
• Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings

  2006cited by this paper
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 1 (Extended Abstract)

  2005cited by this paper
• The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/

  2005cited by this paper
• Approximating rank-width and clique-width quickly

  2005cited by this paper
• Parameterized graph separation problems

  2004cited by this paper
• Graphcut textures: image and video synthesis using graph cuts

  2003cited by this paper
• New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k -Disjoint Cycles on Plane and Planar Graphs

  2002cited by this paper
• How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time

  2001cited by this paper
• Upper bounds to the clique width of graphs

  2000influential reference
• Graph Theory

  1997cited by this paper
• Treewidth

  1994cited by this paper
• Partitioning Planar Graphs

  1992cited by this paper
• The k-section of Treewidth Restricted Graphs

  1990cited by this paper
• Mathematical Foundations of Computer Science 1990

  1990cited by this paper
• Graph bisection algorithms with good average case behavior

  1984cited by this paper
• A Framework for Solving VLSI Graph Layout Problems

  1983cited by this paper
• Graduate Texts in Mathematics

  1982cited by this paper
• On partitioning a graph: a theoretical and empirical study.

  1978cited by this paper
• Applications of a planar separator theorem

  1977cited by this paper
• Some Simplified NP-Complete Graph Problems

  1976cited by this paper
• State of the art in scientific computing

  1963cited by this paper

• Various Properties of Various Ultrafilters, Various Graph Width Parameters, and Various Connectivity Systems

  2024cites this paper
• A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs

  2021cites this paper
• Bisection of Bounded Treewidth Graphs by Convolutions

  2021cites this paper
• Exploiting Dense Structures in Parameterized Complexity

  2021cites this paper
• A survey of parameterized algorithms and the complexity of edge modification

  2020cites this paper
• New Abilities and Limitations of Spectral Graph Bisection

  2017cites this paper
• Abilities and Limitations of Spectral Graph Bisection

  2017cites this paper
• On the complexity of computing the k-restricted edge-connectivity of a graph

  2015cites this paper
• An O(n4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^4)$$\end{document} Time Algorithm to Compute the Bisection

  2014cites this paper
• Minimum bisection is fixed parameter tractable

  2013cites this paper
• On the Parameterized Complexity of Computing Balanced Partitions in Graphs

  2013cites this paper