English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Algorithms for Enumerating Circuits in Matroids.

Boros, E., Elbassioni, K. M., Gurvich, V., & Khachiyan, L. (2003). Algorithms for Enumerating Circuits in Matroids. In Algorithms and Computation (pp. 485-494). Berlin: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-ED43-6 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-ED45-2
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Boros, Endre1, Author
Elbassioni, Khaled M.2, Author           
Gurvich, Vladimir1, Author
Khachiyan, Leonid1, Author
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We present an incremental polynomial-time algorithm for enumerating all circuits of a matroid or, more generally, all minimal spanning sets for a flat. This result implies, in particular, that for a given infeasible system of linear equations, all its maximal feasible subsystems, as well as all minimal infeasible subsystems, can be enumerated in incremental polynomial time. We also show the NP-hardness of several related enumeration problems.

Details

show
hide
Language(s): eng - English
 Dates: 2003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: Elbassioni2003c
DOI: 10.1007/978-3-540-24587-2_50
 Degree: -

Event

show
hide
Title: ISAAC 2003
Place of Event: Kyoto, Japan
Start-/End Date: 2003-12-15 - 2003-12-17

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms and Computation
  Abbreviation : ISAAC 2003
  Subtitle : 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. Proceedings
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 485 - 494 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2906 Sequence Number: - Start / End Page: - Identifier: -