Search results for "matroid"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
124	James B. Orlin	A Fast, Simpler Algorithm for the Matroid Parity Problem.	IPCO	2008	DBLP DOI BibTeX RDF	Matroid parity, matroid matching, matroid intersection, nonbipartite matching
109	Jon Lee 0001, Maxim Sviridenko, Jan Vondrák	Matroid matching: the power of local search.	STOC	2010	DBLP DOI BibTeX RDF	Sherali-Adams hierarchy, local search, matching, matroid
91	Piotr Berman, Martin Fürer, Alexander Zelikovsky	Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees.	CSR	2006	DBLP DOI BibTeX RDF	parity matroid problem, Steiner trees, matroid, approximation ratio
90	B. V. Raghavendra Rao, Jayalal Sarma	On the Complexity of Matroid Isomorphism Problems.	CSR	2009	DBLP DOI BibTeX RDF
84	Petr Hlinený	On Matroid Representability and Minor Problems.	MFCS	2006	DBLP DOI BibTeX RDF	Matroid representability, spike, swirl. 2000 Math subject classification: 05B35, finite field, 68Q17, 68R05, minor
72	Petr Hlinený	On Matroid Properties Definable in the MSO Logic.	MFCS	2003	DBLP DOI BibTeX RDF	MSO logic, parametrized complexity, matroid, branch-width
65	Dániel Marx	A Parameterized View on Matroid Optimization Problems.	ICALP (1)	2006	DBLP DOI BibTeX RDF
65	Tamás Fleiner	A Matroid Generalization of the Stable Matching Polytope.	IPCO	2001	DBLP DOI BibTeX RDF
63	Amos Beimel, Noam Livne, Carles Padró	Matroids Can Be Far from Ideal Secret Sharing.	TCC	2008	DBLP DOI BibTeX RDF
63	Francisco Santos	On Delaunay Oriented Matroids for Convex Distance Functions.	Discret. Comput. Geom.	1996	DBLP DOI BibTeX RDF
57	Petr Hlinený	Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids.	STACS	2003	DBLP DOI BibTeX RDF	representable matroid, fixed-parameter complexity, Classification: parametrized complexity and logic in computer science. (Math subjects 05B35, 68R05, 03D05.), monadic second-order logic, branch-width
57	Anthony J. Roy, John G. Stell	Convexity in Discrete Space.	COSIT	2003	DBLP DOI BibTeX RDF	Convexity axioms, alignment spaces, affine spaces, convex spaces, matroid algorithms, convex hull, discrete geometry, cell complexes, oriented matroids
52	Jon Lee 0001, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko	Non-monotone submodular maximization under matroid and knapsack constraints.	STOC	2009	DBLP DOI BibTeX RDF	approximation algorithms, matroids, knapsacks, submodular functions
52	Taneli Mielikäinen, Esko Ukkonen	The Complexity of Maximum Matroid-Greedoid Intersection.	FCT	2001	DBLP DOI BibTeX RDF
52	Takeaki Uno	A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases.	COCOON	1999	DBLP DOI BibTeX RDF
52	Ying Xu 0001, Harold N. Gabow	Fast Algorithms for Transversal Matroid Intersection Problems	ISAAC	1994	DBLP DOI BibTeX RDF
52	Toshihiro Fujito	A 2or3-Approximation of the Matroid Matching Problem.	ISAAC	1993	DBLP DOI BibTeX RDF
52	Ping Li 0064, Guizhen Liu	The Edge Connectivity of Circuit Graphs of Matroids.	International Conference on Computational Science (3)	2007	DBLP DOI BibTeX RDF	circuit graph of matroid, Matroid, edge connectivity
50	Amos Beimel, Noam Livne	On Matroids and Nonideal Secret Sharing.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
50	Jan Vondrák	Optimal approximation for the submodular welfare problem in the value oracle model.	STOC	2008	DBLP DOI BibTeX RDF	combinatorial auctions, matroids, submodular functions
50	Satoru Iwata 0001, Kenjiro Takazawa	The independent even factor problem.	SODA	2007	DBLP BibTeX RDF
50	Moshe Babaioff, Nicole Immorlica, Robert Kleinberg	Matroids, secretary problems, and online mechanisms.	SODA	2007	DBLP BibTeX RDF
50	Amos Beimel, Noam Livne	On Matroids and Non-ideal Secret Sharing.	TCC	2006	DBLP DOI BibTeX RDF
50	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	Pure Nash Equilibria in Player-Specific and Weighted Congestion Games.	WINE	2006	DBLP DOI BibTeX RDF
50	Siaw-Lynn Ng	A Representation of a Family of Secret Sharing Matroids.	Des. Codes Cryptogr.	2003	DBLP DOI BibTeX RDF	projective geometry, matroids, ideal secret sharing schemes
47	Joachim Reichel, Martin Skutella	Evolutionary algorithms and matroid optimization problems.	GECCO	2007	DBLP DOI BibTeX RDF	matroid intersection, minimum weight basis, evolutionary algorithms, matroids, randomized search heuristics
45	Frederik Armknecht, Matthias Krause 0001	Constructing Single- and Multi-output Boolean Functions with Maximal Algebraic Immunity.	ICALP (2)	2006	DBLP DOI BibTeX RDF	matroid union algorithm, boolean functions, algebraic attacks, Cryptographic primitives
40	Nicholas J. A. Harvey	An algebraic algorithm for weighted linear matroid intersection.	SODA	2007	DBLP BibTeX RDF
40	Nicholas J. A. Harvey	Algebraic Structures and Algorithms for Matching and Matroid Problems.	FOCS	2006	DBLP DOI BibTeX RDF
40	James F. Geelen, Satoru Iwata 0001	Matroid Matching Via Mixed Skew-Symmetric Matrices.	Comb.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C70
40	Bianca Spille, Robert Weismantel	A Generalization of Edmonds' Matching and Matroid Intersection Algorithms.	IPCO	2002	DBLP DOI BibTeX RDF
40	Shusaku Tsumoto	Rule and Matroid Theory.	COMPSAC	2002	DBLP DOI BibTeX RDF
40	Robert T. Firla, Bianca Spille, Robert Weismantel	Algorithmic Characterization of Bipartite b-Matching and Matroid Intersection.	Combinatorial Optimization	2001	DBLP DOI BibTeX RDF
40	Jovan Dj. Golic	On Matroid Characterization of Ideal Secret Sharing Schemes.	J. Cryptol.	1998	DBLP DOI BibTeX RDF	Matroids, Matroids, Key words, Ideal secret sharing schemes, Ideal secret sharing schemes, Access structures, Access structures
40	David Eppstein	Geometric Lower Bounds for Parametric Matroid Optimization.	Discret. Comput. Geom.	1998	DBLP DOI BibTeX RDF
40	Alexander Barg	The Matroid of Supports of A Linear Code.	Appl. Algebra Eng. Commun. Comput.	1997	DBLP DOI BibTeX RDF	Support weight distributions, Mac-Williams equation, Tutte polynomial
40	Peter Kleinschmidt, Shmuel Onn	Oriented Matroid Polytopes and Polyhedral Fans are Signable.	IPCO	1995	DBLP DOI BibTeX RDF
40	Harold N. Gabow, Matthias F. M. Stallmann	Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract).	ICALP	1985	DBLP DOI BibTeX RDF
39	Vladimir I. Danilov, Gleb A. Koshevoy	Choice Functions and Extensive Operators.	Order	2009	DBLP DOI BibTeX RDF	Pre-topology, Anti-matroid, Exchange and anti-exchange conditions, Matroid, Closure operator, Neighborhood system, Direct image
38	Jaume Martí-Farré, Carles Padró	Ideal secret sharing schemes whose minimal qualified subsets have at most three participants.	Des. Codes Cryptogr.	2009	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 94A62, 05B35
38	Mijail Borges-Quintana, Miguel A. Borges-Trenard, Edgar Martínez-Moro	Gröbner Representations of Binary Matroids.	AAECC	2009	DBLP DOI BibTeX RDF
38	Jaume Martí-Farré, Carles Padró	On Secret Sharing Schemes, Matroids and Polymatroids.	TCC	2007	DBLP DOI BibTeX RDF	Ideal access structures, Secret sharing, Matroids, Ideal secret sharing schemes, Information rate, Polymatroids
38	Balázs Szegedy, Christian Szegedy	Symplectic Spaces And Ear-Decomposition Of Matroids.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C70, 05C85, 05C50
38	Satoru Fujishige, Satoru Iwata 0001	Bisubmodular Function Minimization.	IPCO	2001	DBLP DOI BibTeX RDF
38	Takeaki Uno	A New Approach for Speeding Up Enumeration Algorithms.	ISAAC	1998	DBLP DOI BibTeX RDF
38	Kaoru Kurosawa, Koji Okada, Keiichi Sakano, Wakaha Ogata, Shigeo Tsujii	Nonperfect Secret Sharing Schemes and Matroids.	EUROCRYPT	1993	DBLP DOI BibTeX RDF
32	Andrew Brzezinski, Gil Zussman, Eytan H. Modiano	Distributed throughput maximization in wireless mesh networks via pre-partitioning.	IEEE/ACM Trans. Netw.	2008	DBLP DOI BibTeX RDF	local pooling, matroid intersection, scheduling, distributed algorithms, stability, channel assignment
32	Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino	Generating Cut Conjunctions in Graphs and Related Problems.	Algorithmica	2008	DBLP DOI BibTeX RDF	Cut conjunction, Cut generation, Graph, Matroid, Multicut
32	Petr Hlinený, Sang-il Oum	Finding Branch-Decompositions and Rank-Decompositions.	ESA	2007	DBLP DOI BibTeX RDF	Rank-width, fixed parameter tractable algorithm, graph, matroid, clique-width, branch-width
32	Andrew Brzezinski, Gil Zussman, Eytan H. Modiano	Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach.	MobiCom	2006	DBLP DOI BibTeX RDF	local pooling, matroid intersection, scheduling, distributed algorithms, stability, wireless mesh networks, channel assignment
32	Zhenghao Zhang, Yuanyuan Yang	Optimal Scheduling Algorithms in WDM Optical Interconnects with Limited Range Wavelength Conversion Capability.	Asia-Pacific Computer Systems Architecture Conference	2004	DBLP DOI BibTeX RDF	scheduling, bipartite graphs, optical interconnects, Wavelength-division-multiplexing (WDM), matroid, wavelength conversion, bipartite matching, limited range wavelength conversion
32	Petr Hlinený, Detlef Seese	On Decidability of MSO Theories of Representable Matroids.	IWPEC	2004	DBLP DOI BibTeX RDF	MSO theory, decidability, matroid, branch-width
32	Dan Gusfield	Haplotyping as perfect phylogeny: conceptual framework and efficient solutions.	RECOMB	2002	DBLP DOI BibTeX RDF	graph realization, graphic matroid recognition, haplotype inference, perfect phylogeny
32	Ulrich Faigle, Walter Kern	An Order-theoretic Framework for the Greedy Algorithm with Applications to the Core and Weber Set of Cooperative Games.	Order	2000	DBLP DOI BibTeX RDF	antimatroid, coöperative game, Monge algorithm, Weber set, greedy algorithm, core, poset, matroid, submodular
29	Benjamin Jany	The Projectivization Matroid of a \(\boldsymbol{q}\) -Matroid.	SIAM J. Appl. Algebra Geom.	2023	DBLP DOI BibTeX RDF
29	Richard Santiago, Ivan Sergeev, Rico Zenklusen	Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid.	CoRR	2023	DBLP DOI BibTeX RDF
29	Michaela Borzechowski, Simon Weber 0001	On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem.	CoRR	2023	DBLP DOI BibTeX RDF
29	Richard Santiago, Ivan Sergeev, Rico Zenklusen	Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid.	IPCO	2023	DBLP DOI BibTeX RDF
29	Benjamin Jany	The Projectivization Matroid of a q-Matroid.	CoRR	2022	DBLP DOI BibTeX RDF
29	Michael Bamiloshin, Aner Ben-Efraim, Oriol Farràs, Carles Padró	Common information, matroid representation, and secret sharing for matroid ports.	Des. Codes Cryptogr.	2021	DBLP DOI BibTeX RDF
29	Moein Pourbaba, Habib Azanchiler, Ghodratolah Azadi	A new matroid constructed by the rank function of a matroid.	AKCE Int. J. Graphs Comb.	2020	DBLP DOI BibTeX RDF
29	Michael Bamiloshin, Aner Ben-Efraim, Oriol Farràs, Carles Padró	Common Information, Matroid Representation, and Secret Sharing for Matroid Ports.	CoRR	2020	DBLP BibTeX RDF
29	Csaba Király 0001, Zoltán Szigeti, Shin-ichi Tanigawa	Packing of arborescences with matroid constraints via matroid intersection.	Math. Program.	2020	DBLP DOI BibTeX RDF
29	Jinyu Huang	Parallel algorithms for matroid intersection and matroid parity.	Discret. Math. Algorithms Appl.	2015	DBLP DOI BibTeX RDF
29	Jinyu Huang	Parallel Complexity for Matroid Intersection and Matroid Parity Problems.	Electron. Colloquium Comput. Complex.	2012	DBLP BibTeX RDF
29	Yanfang Liu, William Zhu 0001	The role of covering matroid in covering-based rough set and matroid	CoRR	2012	DBLP BibTeX RDF
29	Hong-Jian Lai, Hongyuan Lai	Every Matroid Is a Submatroid of a Uniformly Dense Matroid.	Discret. Appl. Math.	1995	DBLP DOI BibTeX RDF
29	Alexander I. Barvinok	New algorithms for linear k-matroid intersection and matroid k-parity problems.	Math. Program.	1995	DBLP DOI BibTeX RDF
29	James B. Orlin, John H. Vande Vate	Solving the Linear Matroid Parity Problem as a Sequence of Matroid Intersection Problems.	Math. Program.	1990	DBLP DOI BibTeX RDF
29	Horst W. Hamacher	A time expanded matroid algorithm for finding optimal dynamic matroid intersections.	Z. Oper. Research	1985	DBLP DOI BibTeX RDF
29	Annie Astié-Vidal	Factor group of the automorphism group of a matroid basis graph with respect to the automorphism group of the matroid.	Discret. Math.	1980	DBLP DOI BibTeX RDF
27	Jonah Blasiak	The toric ideal of a graphic matroid is generated by quadrics.	Comb.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05B35, 05C05
27	André Berger, Vincenzo Bonifaci, Fabrizio Grandoni 0001, Guido Schäfer	Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle.	IPCO	2008	DBLP DOI BibTeX RDF
27	Nicholas J. A. Harvey	Matroid intersection, pointer chasing, and Young's seminormal representation of Sn.	SODA	2008	DBLP BibTeX RDF
27	Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák	Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract).	IPCO	2007	DBLP DOI BibTeX RDF
27	Manoel Lemos	Weight Distribution of the Bases of a Matroid.	Graphs Comb.	2006	DBLP DOI BibTeX RDF
27	Xun Dong	On the Bounded Complex of an Affine Oriented Matroid.	Discret. Comput. Geom.	2006	DBLP DOI BibTeX RDF
27	Sergey Bereg	Algorithms for the d-Dimensional Rigidity Matroid of Sparse Graphs.	JCDCG	2004	DBLP DOI BibTeX RDF
27	Francesc Serratosa, Antoni Grau, Alberto Sanfeliu	Distance between 2D-Scenes based on Oriented Matroid Theory.	ICPR (2)	2004	DBLP DOI BibTeX RDF
27	Víctor Dalmau, Daniel K. Ford	Generalized Satisfability with Limited Occurrences per Variable: A Study through Delta-Matroid Parity.	MFCS	2003	DBLP DOI BibTeX RDF
27	Ernesto Staffetti, Antoni Grau, Francesc Serratosa, Alberto Sanfeliu	Shape Representation and Indexing Based on Region Connection Calculus and Oriented Matroid Theory.	DGCI	2003	DBLP DOI BibTeX RDF
27	Kenji Kashiwabara, Yoshio Okamoto, Takeaki Uno	Matroid Representation of Clique Complexes.	COCOON	2003	DBLP DOI BibTeX RDF
27	Alexander Golynski, Joseph Douglas Horton	A Polynomial Time Algorithm to Find the Minimum Cycle Basis of a Regular Matroid.	SWAT	2002	DBLP DOI BibTeX RDF
27	T. Ramalingom, Krishnaiyan Thulasiraman, Anindya Das	A Matroid-Theoretic Solution to an Assignment Problem in the Conformance Testing of Communication Protocols.	IEEE Trans. Computers	2000	DBLP DOI BibTeX RDF	algorithms, communication, Protocol, graph theory, communication protocol, matroids, protocol testing
27	Oliver Kullmann	An Application of Matroid Theory to the SAT Problem.	CCC	2000	DBLP DOI BibTeX RDF
27	Felipe Fernández, Ángel Sánchez	Application of Multidimensional Retiming and Matroid Theory to DSP Algorithm Parallelization.	EUROMICRO	1999	DBLP DOI BibTeX RDF
27	Greg N. Frederickson, Roberto Solis-Oba	Algorithms for Measuring Perturbability in Matroid Optimization.	Comb.	1998	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 05B35, 0504, 68R05
27	David Peleg	Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees.	ICALP	1998	DBLP DOI BibTeX RDF
27	Qicheng Yu, Carl Sechen	Efficient approximation of symbolic network functions using matroid intersection algorithms.	IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.	1997	DBLP DOI BibTeX RDF
25	Shaddin Dughmi, Tim Roughgarden, Mukund Sundararajan	Revenue Submodularity.	AMMA	2009	DBLP DOI BibTeX RDF
25	Moshe Babaioff, Jason D. Hartline, Robert D. Kleinberg	Selling ad campaigns: online algorithms with cancellations.	EC	2009	DBLP DOI BibTeX RDF	costly decision revocation, selling advertisements, online algorithms, matroids, knapsack
25	Shaddin Dughmi, Tim Roughgarden, Mukund Sundararajan	Revenue submodularity.	EC	2009	DBLP DOI BibTeX RDF	market expansion, efficiency, monotonicity, trade-offs, revenue, submodularity, vcg, optimal auctions
25	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	On the impact of combinatorial structure on congestion games.	J. ACM	2008	DBLP DOI BibTeX RDF	convergence, local search, Nash equilibria, Congestion games
25	Navin Kashyap	A Decomposition Theory for Binary Linear Codes.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
25	Tamás Király, Lap Chi Lau, Mohit Singh	Degree Bounded Matroids and Submodular Flows.	IPCO	2008	DBLP DOI BibTeX RDF
25	Matthew Cary, Abraham D. Flaxman, Jason D. Hartline, Anna R. Karlin	Auctions for structured procurement.	SODA	2008	DBLP BibTeX RDF
25	Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, Berthold Vöcking	A Unified Approach to Congestion Games and Two-Sided Markets.	WINE	2007	DBLP DOI BibTeX RDF
25	Mark Jerrum	Two Remarks Concerning Balanced Matroids.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05B35, 05A99, 51E10, 68Q17
25	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	On the Impact of Combinatorial Structure on Congestion Games.	FOCS	2006	DBLP DOI BibTeX RDF
25	Iwan M. Duursma	Combinatorics of the Two-Variable Zeta Function.	International Conference on Finite Fields and Applications	2003	DBLP DOI BibTeX RDF