Complexity of maximum cut on interval graphs
From MaRDI portal
Publication:6174803
DOI10.1007/s00454-022-00472-yarXiv2006.00061OpenAlexW3029513181MaRDI QIDQ6174803
Satwik Mukherjee, Kaustav Bose, Ranendu Adhikary, Bodhayan Roy
Publication date: 17 August 2023
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2006.00061
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
MaxCut on permutation graphs is NP‐complete ⋮ Maximum cut on interval graphs of interval count four is NP-complete ⋮ Complexity of maximum cut on interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- \textsc{max-cut} and containment relations in graphs
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
- The max-cut problem on graphs not contractible to \(K_ 5\)
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Finding Hamiltonian circuits in interval graphs
- Optimization, approximation, and complexity classes
- Generalized vertex covering in interval graphs
- Maximum cut on line and total graphs
- Achromatic number is NP-complete for cographs and interval graphs
- Algorithmic graph theory and perfect graphs
- Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
- An improved fixed-parameter algorithm for max-cut parameterized by crossing number
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- The harmonious coloring problem is NP-complete for interval and permutation graphs
- A short proof of the NP-completeness of minimum sum interval coloring
- A new representation of proper interval graphs with an application to clique-width
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- On the power of unique 2-prover 1-round games
- The NP-completeness column: an ongoing guide
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Gadgets, Approximation, and Linear Programming
- Reducibility among Combinatorial Problems
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Some optimal inapproximability results
- Optimal Linear Arrangement of Interval Graphs
- Complexity of maximum cut on interval graphs
This page was built for publication: Complexity of maximum cut on interval graphs