Premium
An algorithm for constructing edge‐trees from hypergraphs
Author(s) -
Gavril Fǎnicǎ,
Tamari Robert
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130306
Subject(s) - hypergraph , combinatorics , mathematics , matroid , enhanced data rates for gsm evolution , time complexity , tree (set theory) , path (computing) , set (abstract data type) , discrete mathematics , algorithm , computer science , artificial intelligence , programming language
Consider a hypergraph H = (E, P) where E denotes the set of vertices and P the set of edges. The hypergraph H = ( E, P ) is called an edge‐tree hypergraph if there exists a tree T with edge set E such that every p = P is a path in T. We describe a polynomial time algorithm for deciding whether a given hypergraph H = ( E, P ) is an edge‐tree hypergraph. The algorithm can be used to decide whether a binary matroid is graphic or not.