The maximum k-colorable subgraph problem for chordal graphs
From MaRDI portal
Publication:1108038
DOI10.1016/0020-0190(87)90107-4zbMATH Open0653.68070OpenAlexW2062221600MaRDI QIDQ1108038FDOQ1108038
Authors: Mihalis Yannakakis, Fanica Gavril 
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(87)90107-4
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- The ellipsoid method and its consequences in combinatorial optimization
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Node-Deletion Problems on Bipartite Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- `` Strong NP-Completeness Results
- On chain and antichain families of a partially ordered set
- Some partitions associated with a partially ordered set
- The structure of Sperner k-families
- Title not available (Why is that?)
Cited In (70)
- Maximum bipartite subgraphs of geometric intersection graphs
- Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
- Minimum weight feedback vertex sets in circle \(n\)-gon graphs and circle trapezoid graphs
- On the parameterized complexity of interval scheduling with eligible machine sets
- Maximum subgraph problem for 3-regular Knödel graphs and its wirelength
- Maximizing dominance in the plane and its applications
- Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs
- MIP formulations for induced graph optimization problems: a tutorial
- Improved Inapproximability Results for Maximum k-Colorable Subgraph
- Heterogeneous Multi-resource Allocation with Subset Demand Requests
- The optimal cost chromatic partition problem for trees and interval graphs
- Algorithmic aspects of clique-transversal and clique-independent sets
- On inverse chromatic number problems (extended abstract)
- Contracting chordal graphs and bipartite graphs to paths and trees
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Maximum weightk-independent set problem on permutation graphs
- A sequential algorithm for finding a maximum weightK-independent set on interval graphs
- The just-in-time scheduling problem in a flow-shop scheduling system
- Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
- “Rent-or-Buy” Scheduling and Cost Coloring Problems
- Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
- Minimum entropy combinatorial optimization problems
- Minimum entropy combinatorial optimization problems
- Minimum weight feedback vertex sets in circle graphs
- Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
- Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
- Clique partitioning of interval graphs with submodular costs on the cliques
- New upper bounds on feedback vertex numbers in butterflies
- Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- Approximation algorithms for maximum weight k-coverings of graphs by packings
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Maximum \(h\)-colourable subgraph problem in balanced graphs
- On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
- Vertex deletion problems on chordal graphs
- Weighted sum coloring in batch scheduling of conflicting jobs
- Maximum max-k-clique subgraphs in cactus subtree graphs
- Approximation results for the optimum cost chromatic partition problem
- On the \(k\)-coloring of intervals
- Inverse chromatic number problems in interval and permutation graphs
- Inductive graph invariants and approximation algorithms
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- The complexity of generalized clique covering
- Parameterized and exact algorithms for class domination coloring
- Maximal chordal subgraphs
- Parameterized and exact algorithms for class domination coloring
- The off-line group seat reservation problem
- Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
- The maximum vertex coverage problem on bipartite graphs
- On the complexity of the selective graph coloring problem in some special classes of graphs
- Vertex deletion problems on chordal graphs
- Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
- The 0-1 inverse maximum stable set problem
- Graph coloring with rejection
- Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
- Refined algorithms for hitting many intervals
- Optimal channel allocation for several types of cellular radio networks
- Just-in-time scheduling with controllable processing times on parallel machines
- Reconfiguration of colorable sets in classes of perfect graphs
- Contracting chordal graphs and bipartite graphs to paths and trees
- Large Induced Subgraphs via Triangulations and CMSO
- Finding a maximum-weight convex set in a chordal graph
- Fair allocation of indivisible items with conflict graphs
- Faster exact algorithms for some terminal set problems
- Solving the single step graph searching problem by solving the maximum two-independent set problem
- Efficient algorithms for the double traveling salesman problem with multiple stacks
- A faster algorithm to recognize undirected path graphs
This page was built for publication: The maximum k-colorable subgraph problem for chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108038)
