Max-Cut Parameterized Above the Edwards-Erdős Bound

2014/01/23 by Robert Crowston, Mark Jones, Matthias Mnich · 19 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Exponential time hypothesis #Graph #Graph Labeling and Dimension Problems #Mathematics #Parameterized complexity #Polynomial #Running time #Theory of computation #Time complexity #Upper and lower bounds

paper · doi:10.1007/s00453-014-9870-z

published in Algorithmica 72(3), 734-757 (Springer Science and Business Media LLC)

openalex publication_date 2014/01/23 · crossref created 2014/01/23 · crossref issued 2014/01/24 · crossref published 2014/01/24 · crossref published-online 2014/01/24 · crossref published-print 2015/07/01 · crossref deposited 2019/08/06 · openalex created_date 2025/10/10 · crossref indexed 2026/02/02 · openalex updated_date 2026/08/06

Citations

• Simultaneously Satisfying Linear Equations Over \mathbbF₂: MaxLin2 and Max-r-Lin2 Parameterized Above Average
• Parameterized Complexity Theory
• Algorithm 447: efficient algorithms for graph manipulation
• Some Extremal Properties of Bipartite Subgraphs
• Distance-hereditary graphs
• On problems without polynomial kernels
• Maximizing Quadratic Programs: Extending Grothendieck's Inequality
• Reducibility among Combinatorial Problems
• Parameterized Complexity

Cited by

• Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
• Maximum balanced subgraph problem parameterized above lower bound
• Maximum cut [wikipedia]