An Efficient Test for Circular-Arc Graphs
From MaRDI portal
Publication:3900112
DOI10.1137/0209001zbMath0453.05054OpenAlexW1980392938WikidataQ60307435 ScholiaQ60307435MaRDI QIDQ3900112
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209001
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Algorithms in computer science (68W99)
Related Items (48)
Circular-arc graphs with clique cover number two ⋮ The Complexity of Coloring Circular Arcs and Chords ⋮ Periodic assignment and graph colouring ⋮ Intersection graphs of concatenable subtrees of graphs ⋮ On the structure of certain intersection graphs ⋮ Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Tree loop graphs ⋮ An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs ⋮ On powers of circular arc graphs and proper circular arc graphs ⋮ Contact Representations of Planar Graphs: Extending a Partial Representation is Hard ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ The complexity of colouring circle graphs ⋮ Extending partial representations of circular-arc graphs ⋮ New characterizations of proper interval bigraphs ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ 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) ⋮ Two remarks on circular arc graphs ⋮ Parallel algorithms on circular-arc graphs ⋮ Precoloring extension. I: Interval graphs ⋮ Minimum entropy combinatorial optimization problems ⋮ A model predictive control approach for discrete-time rescheduling in complex central railway station areas ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ A short proof of the NP-completeness of minimum sum interval coloring ⋮ An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs ⋮ Algorithms for clique-independent sets on subclasses of circular-arc graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Completing colored graphs to meet a target property ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Minimum entropy coloring ⋮ Optimal parallel algorithms on circular-arc graphs ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ Linear-Time Recognition of Probe Interval Graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Lexicographic Orientation Algorithms ⋮ Finding Hamiltonian circuits in proper interval graphs ⋮ On a circle-cover minimization problem ⋮ An O(qn) algorithm to q-color a proper family of circular arcs ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm ⋮ Efficient reduction for path problems on circular-arc graphs ⋮ Dominating sets and domatic number of circular arc graphs ⋮ An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs ⋮ Graphs and digraphs represented by intervals and circular arcs
This page was built for publication: An Efficient Test for Circular-Arc Graphs
