A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases | Zendy

Takeaki Uno | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases

Author(s) -

Takeaki Uno

Publication year - 1999

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-66200-6

DOI - 10.1007/3-540-48686-0_35

Subject(s) - enumeration , matroid , bipartite graph , oriented matroid , matroid partitioning , weighted matroid , matching (statistics) , combinatorics , graphic matroid , rank (graph theory) , time complexity , computation , base (topology) , computer science , algorithm , discrete mathematics , mathematics , graph , mathematical analysis , statistics

We propose a new approach for speeding up enumeration algorithms. The approach does not rely on data structures deeply, instead utilizes analysis of computation time. It speeds enumeration algorithms for directed spanning trees, matroid bases, and some bipartite matching problems. We show one of these improved algorithms: one for enumerating matroid bases. For a given matroid M with m elements and rank n an existing algorithm runs in O(T) time per base. We improved the time complexity to O(T/n), or O(T/m(m - n)).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research