scientific article; zbMATH DE number 437537

MaRDI QIDQ3140413zbMATH OpenFDO

Authors Elaine M. Eschen, Jeremy P. Spinrad

Publication date 15 December 1993

zbMATH Keywords

chordal bipartite graphscircular-arc graphsgraph recognition algorithm

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Linear-time recognition of circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• A simpler linear-time recognition of circular-arc graphs
• Practical and efficient circle graph recognition

Cited in

(28)

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Circular-arc graphs with clique cover number two
• Linear-time recognition of circular-arc graphs
• An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
• Algorithms for induced biclique optimization problems
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Fully dynamic recognition of proper circular-arc graphs
• Doubly lexical ordering of dense 0--1 matrices
• Paired domination on interval and circular-arc graphs
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Colouring Some Classes of Perfect Graphs Robustly
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• On Three Constrained Versions of the Digital Circular Arc Recognition Problem
• O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Polynomial time recognition of unit circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Circular-arc graph coloring: On chords and circuits in the meeting graph
• Maximum max-k-clique subgraphs in cactus subtree graphs
• A simpler linear-time recognition of circular-arc graphs
• Two remarks on circular arc graphs
• A characterization of uniquely representable two-directional orthogonal ray graphs
• Graph classes equivalent to 12-representable graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• BOB: Improved winner determination in combinatorial auctions and generalizations
• On the structure of certain intersection graphs
• Tree loop graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140413)