6533b7dcfe1ef96bd12733ac

RESEARCH PRODUCT

An Efficient Algorithm for Helly Property Recognition in a Linear Hypergraph

Stéphane UbédaAlain BrettoHocine Cherifi

subject

HypergraphProperty (philosophy)General Computer Science[ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI]0102 computer and information sciences02 engineering and technologyComputer Science::Computational Geometry01 natural sciencesPolynomial algorithmTheoretical Computer ScienceCombinatorics[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI][ INFO.INFO-DC ] Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC]Computer Science::Discrete Mathematics[ INFO.INFO-TI ] Computer Science [cs]/Image Processing0202 electrical engineering electronic engineering information engineeringMathematics::Metric GeometryComputingMilieux_MISCELLANEOUSMathematicsIncidence (geometry)Discrete mathematicsMathematics::CombinatoricsEfficient algorithm16. Peace & justice010201 computation theory & mathematics[INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV]Bipartite graph020201 artificial intelligence & image processing[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC]Computer Science(all)

description

International audience; In this article we characterize bipartite graphs whose associated neighborhood hypergraphs have the Helly property. We examine incidence graphs both hypergraphs and linear hypergraphs and we give a polynomial algorithm to recognize if a linear hypergraph has the Helly property.

yearjournalcountryeditionlanguage
2001-08-01Electronic Notes in Theoretical Computer Science
https://doi.org/10.1016/s1571-0661(04)80985-x