Complexity of maximum cut on interval graphs
From MaRDI portal
(Redirected from Publication:6174803)
Complexity of maximum cut on interval graphs (scientific article; zbMATH DE number 7729235)
Complexity of maximum cut on interval graphs (scientific article; zbMATH DE number 7729235)
Abstract: We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.
Cites work
- \textsc{max-cut} and containment relations in graphs
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- A new representation of proper interval graphs with an application to clique-width
- A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
- A short proof of the NP-completeness of minimum sum interval coloring
- Achromatic number is NP-complete for cographs and interval graphs
- Algorithmic graph theory and perfect graphs
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- An improved fixed-parameter algorithm for max-cut parameterized by crossing number
- Complexity of maximum cut on interval graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Finding Hamiltonian circuits in interval graphs
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
- Gadgets, Approximation, and Linear Programming
- Generalized vertex covering in interval graphs
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- scientific article; zbMATH DE number 7724211 (Why is no real title available?)
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Maximum cut on line and total graphs
- On the power of unique 2-prover 1-round games
- Optimal Linear Arrangement of Interval Graphs
- Optimization, approximation, and complexity classes
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Reducibility among combinatorial problems
- Some optimal inapproximability results
- The harmonious coloring problem is NP-complete for interval and permutation graphs
- The max-cut problem on graphs not contractible to \(K_ 5\)
- The NP-completeness column: an ongoing guide
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
Cited in
(10)- Maximum cutwidth problem for graphs.
- Length-bounded cuts: proper interval graphs and structural parameters
- MaxCut on permutation graphs is NP‐complete
- Maximum cut on interval graphs of interval count four is NP-complete
- scientific article; zbMATH DE number 7724211 (Why is no real title available?)
- Complexity of maximum cut on interval graphs
- Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
- Semi-proper interval graphs
- The maximum clique problem in a disk graph made easy
- Approximating maximum cut on interval graphs and split graphs beyond Goemans-Williamson
This page was built for publication: Complexity of maximum cut on interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174803)
