An optimal greedy heuristic to color interval graphs

DOI10.1016/0020-0190(91)90245-DzbMath0711.68083OpenAlexW2015475193MaRDI QIDQ922724

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90245-d

zbMATH Keywords

interval graphs linear-time algorithms greedy heuristic coloring algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Greedy algorithms for tracking mobile users in special mobility graphs, Optimal greedy algorithms for indifference graphs, Thinness of product graphs, Heterogeneous Multi-resource Allocation with Subset Demand Requests, A linear time algorithm to compute square of interval graphs and their colouring, The stable set problem and the thinness of a graph, Inverse interval scheduling via reduction on a single machine, A new LBFS-based algorithm for cocomparability graph recognition, A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs, On minimum intersection of two minimum dominating sets of interval graphs, Scheduling preparation of doses for a chemotherapy service, Perfect elimination orderings for symmetric matrices, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, Selection of programme slots of television channels for giving advertisement: a graph theoretic approach, On the thinness and proper thinness of a graph, Chronological rectangle digraphs which are two-terminal series-parallel, Independent set under a change constraint from an initial solution, Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs, Computation of diameter, radius and center of permutation graphs, Scheduling light-trails on WDM rings, Bandwidth on AT-free graphs, On coloring problems with local constraints, Hardness and algorithms of equitable tree-coloring problem in chordal graphs, The worst case behavior of randomized gossip protocols, An optimal algorithm to find minimum k-hop dominating set of interval graphs, The Roberts characterization of proper and unit interval graphs, Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs, Solving problems on generalized convex graphs via mim-width, A linear time algorithm to compute a dominating path in an AT-free graph, \(L(2,1)\)-labeling of interval graphs, An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\), Line-distortion, bandwidth and path-length of a graph, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs, Improper coloring of unit disk graphs, Hardness and approximation of minimum distortion embeddings, A Lex-BFS-based recognition algorithm for Robinsonian matrices, Theoretical aspects of equitable partition of networks into sparse modules, Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach, On the Power of Graph Searching for Cocomparability Graphs, Minimal interval completion through graph exploration, Complexity of tree-coloring interval graphs equitably, A vertex ordering characterization of simple-triangle graphs, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, Fleet management for autonomous vehicles: Online PDP under special constraints, Nash equilibria in all-optical networks, Precedence thinness in graphs, Graph Classes and Forbidden Patterns on Three Vertices, Interval scheduling with economies of scale, Minimum r-neighborhood covering set of permutation graphs, Routing and path multicoloring

Cites Work