Linear-time recognition of Helly circular-arc models and graphs

DOI10.1007/S00453-009-9304-5MaRDI QIDQ627542zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Benson Joeris, Min Chih Lin, R. M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter

Publication date 2 March 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-009-9304-5

zbMATH Keywords

algorithmscircular-arc graphsforbidden subgraphsHelly circular-arc graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Proper Helly Circular-Arc Graphs
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Normal Helly circular-arc graphs and its subclasses
• On cliques of Helly Circular-arc Graphs

Cites work

• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Algorithmic graph theory and perfect graphs
• Algorithms on circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Characterizing circular-arc graphs
• Efficient construction of unit circular-arc models
• Efficient graph representations
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time recognition of circular-arc graphs
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Unit Circular-Arc Graph Representations and Feasible Circulations

Cited in

(23)

• On cliques of Helly Circular-arc Graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Extending partial representations of circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
• On neighborhood-Helly graphs
• The Persistent Homology of Cyclic Graphs
• Proper Helly Circular-Arc Graphs
• Balancedness of some subclasses of circular-arc graphs
• Diamond-free circle graphs are Helly circle
• Algorithms for finding clique-transversals of graphs
• Finding intersection models: from chordal to Helly circular-arc graphs
• Essential obstacles to Helly circular-arc graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• From a Circular-Arc Model to a Proper Circular-Arc Model
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Linear-time recognition of circular-arc graphs
• On the isomorphism problem for Helly circular-arc graphs
• Normal Helly circular-arc graphs and its subclasses
• A linear-time algorithm for clique-coloring problem in circular-arc graphs
• Canonical representations for circular-arc graphs using flip sets

This page was built for publication: Linear-time recognition of Helly circular-arc models and graphs

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