The Complexity of Coloring Circular Arcs and Chords

From MaRDI portal
Publication:3964622

DOI10.1137/0601025zbMath0499.05058OpenAlexW2074937107WikidataQ55951939 ScholiaQ55951939MaRDI QIDQ3964622

Michael R. Garey, David S. Johnson, Christos H. Papadimitriou, Gary Lee Miller

Publication date: 1980

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0601025



Related Items

Extending partial representations of circular-arc graphs, Bounding the mim‐width of hereditary graph classes, Maximum max-k-clique subgraphs in cactus subtree graphs, Treewidth versus clique number. II: Tree-independence number, On \(d\)-stable locally checkable problems parameterized by mim-width, The complexity of path coloring and call scheduling, An approximation result for a periodic allocation problem, Circular-arc graph coloring: On chords and circuits in the meeting graph, Complexity and online algorithms for minimum skyline coloring of intervals, The longest common subsequence problem for sequences with nested arc annotations., On the minimum and maximum selective graph coloring problems in some graph classes, Strong edge coloring of circle graphs, Periodic assignment and graph colouring, Improved bounds for colouring circle graphs, MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS, Parameterized Maximum Path Coloring, Two-page book embedding of trees under vertex-neighborhood constraints, A note on optical routing on trees, The chromatic index of proper circular-arc graphs of odd maximum degree which are chordal, Embedding generalized Petersen graph in books, On some applications of the selective graph coloring problem, A survey on book-embedding of planar graphs, Approximating minimum coloring and maximum independent set in dotted interval graphs, Cyclic scheduling in a robotic production line, Subtree filament graphs are subtree overlap graphs, Inverse chromatic number problems in interval and permutation graphs, Exact and heuristic approaches to the airport stand allocation problem, 2-nested matrices: towards understanding the structure of circle graphs, Fixed interval scheduling: models, applications, computational complexity and algorithms, Max point-tolerance graphs, Unnamed Item, Algorithmic aspects of intersection graphs and representation hypergraphs, Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs, Intersection graphs of Helly families of subtrees, Embedding planar graphs in four pages, Embedding Outerplanar Graphs in Small Books, Succinct encodings for families of interval graphs, Parameterized maximum path coloring, The complexity of colouring circle graphs, Hardness and approximation for L-EPG and \(B_1\)-EPG graphs, Algorithms for Necklace Maps, Optimization problems in dotted interval graphs, Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number, The permutation-path coloring problem on trees., Optimal on-line coloring of circular arc graphs, Planar graphs that need four pages, Routing equal-size messages on a slotted ring, On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs, Local and union page numbers, The complexity of register allocation, On coloring problems with local constraints, Induced matchings in intersection graphs., Computing and counting longest paths on circular-arc graphs in polynomial time, Structural results on circular-arc graphs and circle graphs: a survey and the main open problems, Representations of graphs and networks (coding, layouts and embeddings), List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective, Exploring the complexity boundary between coloring and list-coloring, List matrix partitions of graphs representing geometric configurations, Routing permutations and involutions on optical ring networks: Complexity results and solution to an open problem, Efficient parallel recognition of some circular arc graphs. II, Precoloring extension. I: Interval graphs, Independence and domination in polygon graphs, Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy, Minimum weight feedback vertex sets in circle graphs, Minimum entropy combinatorial optimization problems, On the page number of RNA secondary structures with pseudoknots, Efficient parallel recognition of some circular arc graphs. I, A short proof of the NP-completeness of minimum sum interval coloring, On the complexity of interval scheduling with a resource constraint, 1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings, Unnamed Item, Conversion of coloring algorithms into maximum weight independent set algorithms, On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs, Approximating the minimum clique cover and other hard problems in subtree filament graphs, SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS, On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering, Edge-coloring of 3-uniform hypergraphs, Mutual exclusion scheduling with interval graphs or related classes. I, Selfish Routing and Path Coloring in All-Optical Networks, A constant factor approximation algorithm for boxicity of circular arc graphs, On rectangle intersection graphs with stab number at most two, Unnamed Item, Minimum entropy coloring, All structured programs have small tree width and good register allocation, Hadwiger's conjecture for proper circular arc graphs, Jump number maximization for proper interval graphs and series-parallel graphs, Efficient algorithms for wavelength assignment on trees of rings, An \(0(n^{1.5})\) algorithm to color proper circular arcs, Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design, Container ship stowage problem complexity and connection to the coloring of circle graphs, String graphs of k-bend paths on a grid, Weighted coloring: further complexity and approximability results, APX-hardness of domination problems in circle graphs, A weighted graph polynomial from chromatic invariants of knots, Perfect circular arc coloring, Revising Johnson's table for the 21st century, More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints, Distributed interactive proofs for the recognition of some geometric intersection graph classes, An O(qn) algorithm to q-color a proper family of circular arcs, Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times, On the chromatic number of multiple interval graphs and overlap graphs, Independent packings in structured graphs, A simple optimal parallel algorithm for the minimum coloring problem on interval graphs, Dominating sets and domatic number of circular arc graphs, Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis, Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs, The \(k\)-track assignment problem, Routing and path multicoloring, An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs



Cites Work