The Complexity of Coloring Circular Arcs and Chords
From MaRDI portal
Publication:3964622
Cites work
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3420624 (Why is no real title available?)
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Algorithms on circular-arc graphs
- An Efficient Test for Circular-Arc Graphs
- Coloring a Family of Circular Arcs
- Matrix characterizations of circular-arc graphs
- On the Computational Complexity of Combinatorial Problems
- Some simplified NP-complete graph problems
- Structure theorems for some circular-arc graphs
Cited in
(only showing first 100 items - show all)- Extending partial representations of circular-arc graphs
- Precoloring extension. I: Interval graphs
- Periodic assignment and graph colouring
- On the chromatic number of multiple interval graphs and overlap graphs
- Container ship stowage problem complexity and connection to the coloring of circle graphs
- Parameterized maximum path coloring
- On the page number of RNA secondary structures with pseudoknots
- Hadwiger's conjecture for proper circular arc graphs
- Minimum weight feedback vertex sets in circle graphs
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS
- Max point-tolerance graphs
- Succinct encodings for families of interval graphs
- Independence and domination in polygon graphs
- APX-hardness of domination problems in circle graphs
- A note on optical routing on trees
- A constant factor approximation algorithm for boxicity of circular arc graphs
- Optimal on-line coloring of circular arc graphs
- A simple optimal parallel algorithm for the minimum coloring problem on interval graphs
- Efficient parallel recognition of some circular arc graphs. I
- Algorithmic aspects of intersection graphs and representation hypergraphs
- The permutation-path coloring problem on trees.
- String graphs of \(k\)-bend paths on a grid
- Optimization problems in dotted interval graphs
- Embedding Outerplanar Graphs in Small Books
- All structured programs have small tree width and good register allocation
- Subtree filament graphs are subtree overlap graphs
- An approximation result for a periodic allocation problem
- Routing permutations and involutions on optical ring networks: Complexity results and solution to an open problem
- 1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings
- The \(k\)-track assignment problem
- Cyclic scheduling in a robotic production line
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- On inverse chromatic number problems (extended abstract)
- Induced matchings in intersection graphs.
- More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- On the complexity of interval scheduling with a resource constraint
- Jump number maximization for proper interval graphs and series-parallel graphs
- Approximating minimum coloring and maximum independent set in dotted interval graphs
- Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
- On some applications of the selective graph coloring problem
- Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs
- On rectangle intersection graphs with stab number at most two
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
- Embedding planar graphs in four pages
- The complexity of colouring circle graphs (extended abstract)
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Approximating the minimum clique cover and other hard problems in subtree filament graphs
- Exploring the complexity boundary between coloring and list-coloring
- A short proof of the NP-completeness of minimum sum interval coloring
- Edge-coloring of 3-uniform hypergraphs
- Computing and counting longest paths on circular-arc graphs in polynomial time
- The longest common subsequence problem for sequences with nested arc annotations.
- Intersection graphs of Helly families of subtrees
- Weighted coloring: further complexity and approximability results
- Inverse chromatic number problems in interval and permutation graphs
- Minimum entropy combinatorial optimization problems
- Exact and heuristic approaches to the airport stand allocation problem
- The complexity of path coloring and call scheduling
- Independent packings in structured graphs
- Dominating sets and domatic number of circular arc graphs
- Efficient parallel recognition of some circular arc graphs. II
- A weighted graph polynomial from chromatic invariants of knots
- An \(0(n^{1.5})\) algorithm to color proper circular arcs
- Representations of graphs and networks (coding, layouts and embeddings)
- Mutual exclusion scheduling with interval graphs or related classes. I
- An O(qn) algorithm to q-color a proper family of circular arcs
- On the minimum and maximum selective graph coloring problems in some graph classes
- Minimum entropy coloring
- On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs
- Embedding generalized Petersen graph in books
- Conversion of coloring algorithms into maximum weight independent set algorithms
- List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
- Efficient algorithms for wavelength assignment on trees of rings
- Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- Routing equal-size messages on a slotted ring
- Circular-arc graph coloring: On chords and circuits in the meeting graph
- A survey on book-embedding of planar graphs
- Algorithms for Necklace Maps
- Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times
- Multithread interval scheduling with flexible machine availabilities: complexity and efficient algorithms
- On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
- Planar graphs that need four pages
- Selfish Routing and Path Coloring in All-Optical Networks
- Perfect circular arc coloring
- A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
- Local and union page numbers
- The optimal cost chromatic partition problem for trees and interval graphs
- Maximum max-k-clique subgraphs in cactus subtree graphs
- Improved bounds for colouring circle graphs
- On \(d\)-stable locally checkable problems parameterized by mim-width
- Bisimplicial separators
- Treewidth versus clique number. II: Tree-independence number
- 2-nested matrices: towards understanding the structure of circle graphs
- Two-page book embedding of trees under vertex-neighborhood constraints
- Minimum weight feedback vertex sets in circle \(n\)-gon graphs and circle trapezoid graphs
- Bounding the mim‐width of hereditary graph classes
- On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
This page was built for publication: The Complexity of Coloring Circular Arcs and Chords
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3964622)
