Algorithms on circular-arc graphs
From MaRDI portal
Publication:4067141
DOI10.1002/net.3230040407zbMath0309.05126OpenAlexW2048237851WikidataQ60307432 ScholiaQ60307432MaRDI QIDQ4067141
Publication date: 1974
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230040407
Related Items (68)
Circular-arc graphs with clique cover number two ⋮ An exact algorithm for the maximum stable set problem ⋮ The Complexity of Coloring Circular Arcs and Chords ⋮ Periodic assignment and graph colouring ⋮ Intersection graphs of concatenable subtrees of graphs ⋮ Maximum weight independent sets and cliques in intersection graphs of filaments ⋮ Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs, ⋮ Computing the all-pairs longest chains in the plane ⋮ 2-nested matrices: towards understanding the structure of circle graphs ⋮ Maximum weight independent set of circular-arc graph and its application ⋮ On neighborhood-Helly graphs ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Intersection graphs of Helly families of subtrees ⋮ An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs ⋮ Contact Representations of Planar Graphs: Extending a Partial Representation is Hard ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ On some graph classes related to perfect graphs: a survey ⋮ Extending partial representations of circular-arc graphs ⋮ Independent set under a change constraint from an initial solution ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Finding intersection models: from chordal to Helly circular-arc graphs ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Distance-\(d\) independent set problems for bipartite and chordal graphs ⋮ A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Induced matchings in intersection graphs. ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ Intersection representations of matrices by subtrees and unicycles on graphs ⋮ Algorithms for finding clique-transversals of graphs ⋮ 3D-interval-filament graphs ⋮ New clique and independent set algorithms for circle graphs ⋮ Two remarks on circular arc graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Parallel algorithms on circular-arc graphs ⋮ Unit interval editing is fixed-parameter tractable ⋮ A branch and bound algorithm for the maximum clique problem ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ An approximation result for a periodic allocation problem ⋮ Biclique graphs and biclique matrices ⋮ Algorithms for clique-independent sets on subclasses of circular-arc graphs ⋮ Completing colored graphs to meet a target property ⋮ On \(H\)-topological intersection graphs ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Canonical representations for circular-arc graphs using flip sets ⋮ Minimum node disjoint path covering for circular-arc graphs ⋮ Using Fifth Generation Tools for Solving the Clique Number Problem ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ Hadwiger's conjecture for proper circular arc graphs ⋮ Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs ⋮ Algorithms on Subtree Filament Graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Finding Hamiltonian circuits in proper interval graphs ⋮ On a circle-cover minimization problem ⋮ Independent packings in structured graphs ⋮ Characterization and recognition of Helly circular-arc clique-perfect graphs ⋮ Colouring Some Classes of Perfect Graphs Robustly ⋮ Dominating sets and domatic number of circular arc graphs ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ The maximum clique problem ⋮ On the isomorphism problem for Helly circular-arc graphs ⋮ An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
Cites Work
This page was built for publication: Algorithms on circular-arc graphs
