Complexity of maximum cut on interval graphs
From MaRDI portal
Cites work
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- 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
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- 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
- Generalized vertex covering in interval graphs
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- scientific article; zbMATH DE number 7765365 (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
- 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
- Reducibility among combinatorial problems
- 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
(2)
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 Q7234063)
