Search results for "Matroid"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
5	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
4	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
3	Jon Lee, 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
3	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
3	Ping Li, Guizhen Liu	The Edge Connectivity of Circuit Graphs of Matroids.	International Conference on Computational Science	2007	DBLP DOI BibTeX RDF	circuit graph of matroid, Matroid, edge connectivity
3	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
3	Petr Hlinený	On Matroid Properties Definable in the MSO Logic.	MFCS	2003	DBLP DOI BibTeX RDF	MSO logic, parametrized complexity, matroid, branch-width
2	B. V. Raghavendra Rao, Jayalal M. N. Sarma	On the Complexity of Matroid Isomorphism Problems.	CSR	2009	DBLP DOI BibTeX RDF
2	Jon Lee, 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
2	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
2	Jonah Blasiak	The toric ideal of a graphic matroid is generated by quadrics.	Combinatorica	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05B35, 05C05
2	Nicholas J. A. Harvey	Matroid intersection, pointer chasing, and Young's seminormal representation of Sn.	SODA	2008	DBLP DOI BibTeX RDF
2	André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, Guido Schäfer	Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle.	IPCO	2008	DBLP DOI BibTeX RDF
2	Andrew Brzezinski, Gil Zussman, Eytan 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
2	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
2	Nicholas J. A. Harvey	An algebraic algorithm for weighted linear matroid intersection.	SODA	2007	DBLP DOI BibTeX RDF
2	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
2	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
2	Manoel Lemos	Weight Distribution of the Bases of a Matroid.	Graphs and Combinatorics	2006	DBLP DOI BibTeX RDF
2	Xun Dong	On the Bounded Complex of an Affine Oriented Matroid.	Discrete & Computational Geometry	2006	DBLP DOI BibTeX RDF
2	Dániel Marx	A Parameterized View on Matroid Optimization Problems.	ICALP	2006	DBLP DOI BibTeX RDF
2	Nicholas J. A. Harvey	Algebraic Structures and Algorithms for Matching and Matroid Problems.	FOCS	2006	DBLP DOI BibTeX RDF
2	Andrew Brzezinski, Gil Zussman, Eytan 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
2	Frederik Armknecht, Matthias Krause	Constructing Single- and Multi-output Boolean Functions with Maximal Algebraic Immunity.	ICALP	2006	DBLP DOI BibTeX RDF	matroid union algorithm, boolean functions, algebraic attacks, Cryptographic primitives
2	James F. Geelen, Satoru Iwata	Matroid Matching Via Mixed Skew-Symmetric Matrices.	Combinatorica	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C70
2	Francesc Serratosa, Antoni Grau, Alberto Sanfeliu	Distance between 2D-Scenes based on Oriented Matroid Theory.	ICPR	2004	DBLP DOI BibTeX RDF
2	Sergey Bereg	Algorithms for the d-Dimensional Rigidity Matroid of Sparse Graphs.	JCDCG	2004	DBLP DOI BibTeX RDF
2	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
2	Petr Hlinený, Detlef Seese	On Decidability of MSO Theories of Representable Matroids.	IWPEC	2004	DBLP DOI BibTeX RDF	MSO theory, decidability, matroid, branch-width
2	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
2	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
2	Kenji Kashiwabara, Yoshio Okamoto, Takeaki Uno	Matroid Representation of Clique Complexes.	COCOON	2003	DBLP DOI BibTeX RDF
2	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
2	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
2	Shusaku Tsumoto	Rule and Matroid Theory.	COMPSAC	2002	DBLP DOI BibTeX RDF
2	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
2	Bianca Spille, Robert Weismantel	A Generalization of Edmonds' Matching and Matroid Intersection Algorithms.	IPCO	2002	DBLP BibTeX RDF
2	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
2	Taneli Mielikäinen, Esko Ukkonen	The Complexity of Maximum Matroid-Greedoid Intersection.	FCT	2001	DBLP DOI BibTeX RDF
2	Tamás Fleiner	A Matroid Generalization of the Stable Matching Polytope.	IPCO	2001	DBLP DOI BibTeX RDF
2	Robert T. Firla, Bianca Spille, Robert Weismantel	Algorithmic Characterization of Bipartite b-Matching and Matroid Intersection.	Combinatorial Optimization	2001	DBLP DOI BibTeX RDF
2	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
2	Oliver Kullmann	An Application of Matroid Theory to the SAT Problem. (PDF / PS)	IEEE Conference on Computational Complexity	2000	DBLP DOI BibTeX RDF
2	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
2	Takeaki Uno	A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases.	COCOON	1999	DBLP DOI BibTeX RDF
2	Felipe Fernández, Ángel Sánchez	Application of Multidimensional Retiming and Matroid Theory to DSP Algorithm Parallelization.	EUROMICRO	1999	DBLP DOI BibTeX RDF
2	Greg N. Frederickson, Roberto Solis-Oba	Algorithms for Measuring Perturbability in Matroid Optimization.	Combinatorica	1998	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 05B35, 0504, 68R05
2	David Eppstein	Geometric Lower Bounds for Parametric Matroid Optimization.	Discrete & Computational Geometry	1998	DBLP DOI BibTeX RDF
2	Jovan Dj. Golic	On Matroid Characterization of Ideal Secret Sharing Schemes.	J. Cryptology	1998	DBLP DOI BibTeX RDF	Matroids, Matroids, Key words, Ideal secret sharing schemes, Ideal secret sharing schemes, Access structures, Access structures
2	David Peleg	Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees.	ICALP	1998	DBLP DOI BibTeX RDF
2	Qicheng Yu, Carl Sechen	Efficient approximation of symbolic network functions using matroid intersection algorithms.	IEEE Trans. on CAD of Integrated Circuits and Systems	1997	DBLP DOI BibTeX RDF
2	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
2	Peter Kleinschmidt, Shmuel Onn	Oriented Matroid Polytopes and Polyhedral Fans are Signable.	IPCO	1995	DBLP DOI BibTeX RDF
2	Ying Xu, Harold N. Gabow	Fast Algorithms for Transversal Matroid Intersection Problems	ISAAC	1994	DBLP DOI BibTeX RDF
2	Toshihiro Fujito	A 2or3-Approximation of the Matroid Matching Problem.	ISAAC	1993	DBLP DOI BibTeX RDF
2	Harold N. Gabow, Matthias F. M. Stallmann	Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract).	ICALP	1985	DBLP DOI BibTeX RDF
1	Deborah Chun, James G. Oxley, Geoff Whittle	Capturing matroid elements in unavoidable 3-connected minors.	Eur. J. Comb.	2012	DBLP DOI BibTeX RDF
1	Yoshitake Matsumoto, Sonoko Moriyama, Hiroshi Imai, David Bremner	Matroid Enumeration for Incidence Geometry.	Discrete & Computational Geometry	2012	DBLP DOI BibTeX RDF
1	Asaf Cohen, Shlomi Dolev, Guy Leshem	Sensor Networks: from Dependence Analysis Via Matroid Bases to Online Synthesis	CoRR	2012	DBLP BibTeX RDF
1	Robert Kleinberg, S. Matthew Weinberg	Matroid Prophet Inequalities	CoRR	2012	DBLP BibTeX RDF
1	Anthony Nixon	A Constructive Characterisation of Circuits in the Simple (2,2)-sparsity Matroid	CoRR	2012	DBLP BibTeX RDF
1	Yuval Filmus, Justin Ward	A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint	CoRR	2012	DBLP BibTeX RDF
1	Sourav Chakraborty, Oded Lachish	Improved competitive ratio for the matroid secretary problem.	SODA	2012	DBLP BibTeX RDF
1	Konstantin Makarychev, Warren Schudy, Maxim Sviridenko	Concentration inequalities for nonlinear matroid intersection.	SODA	2012	DBLP BibTeX RDF
1	Tamás Fleiner, Naoyuki Kamiyama	A matroid approach to stable matchings with lower quotas.	SODA	2012	DBLP BibTeX RDF
1	Yuval Filmus, Justin Ward	The Power of Local Search: Maximum Coverage over a Matroid.	STACS	2012	DBLP DOI BibTeX RDF
1	Robert Kleinberg, S. Matthew Weinberg	Matroid prophet inequalities.	STOC	2012	DBLP DOI BibTeX RDF
1	José A. Soto	A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids.	Electronic Notes in Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki	Outerplanar Obstructions for Matroid Pathwidth.	Electronic Notes in Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Diana Fanghänel	Optimality conditions for a bilevel matroid problem.	J. Comb. Optim.	2011	DBLP DOI BibTeX RDF
1	Jessica Ruth Metcalf-Burton	Improved upper bounds for the information rates of the secret sharing schemes induced by the Vámos matroid.	Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Jean François Maurras, Rüdiger Stephan	On the cardinality constrained matroid polytope.	Networks	2011	DBLP DOI BibTeX RDF
1	Sushil Bikhchandani, Sven de Vries, James Schummer, Rakesh V. Vohra	An Ascending Vickrey Auction for Selling Bases of a Matroid.	Operations Research	2011	DBLP DOI BibTeX RDF
1	Hong-Jian Lai, Manoel Lemos, Talmage James Reid, Yehong Shao, Haidong Wu	Obstructions to a binary matroid being graphic.	Eur. J. Comb.	2011	DBLP DOI BibTeX RDF
1	Arun P. Mani	An Extension of Matroid Rank Submodularity and the Z-Rayleigh Property.	Electr. J. Comb.	2011	DBLP BibTeX RDF
1	Dingcheng Feng, Feng Chen, Wenli Xu	Analysis of Markov Boundary Induction in Bayesian Networks: A New View From Matroid Theory.	Fundam. Inform.	2011	DBLP DOI BibTeX RDF
1	Santosh N. Kabadi, Abraham P. Punnen	Trioid: A generalization of matroid and the associated polytope.	Algorithmic Operations Research	2011	DBLP BibTeX RDF
1	Shayan Oveis Gharan, Jan Vondrák	On Variants of the Matroid Secretary Problem	CoRR	2011	DBLP BibTeX RDF
1	Naoki Katoh, Shin-ichi Tanigawa	Rooted-tree Decompositions with Matroid Constraints and the Infinitesimal Rigidity of Frameworks with Boundaries	CoRR	2011	DBLP BibTeX RDF
1	José A. Soto	A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids	CoRR	2011	DBLP BibTeX RDF
1	Daniel Golovin, Andreas Krause	Adaptive Submodular Optimization under Matroid Constraints	CoRR	2011	DBLP BibTeX RDF
1	Bo Tang 0003, Yajun Wang	Algorithms for Submodular Matroid Secretary Problems Under Transversal Matroids and Partition Matroids	CoRR	2011	DBLP BibTeX RDF
1	B. V. Raghavendra Rao, Jayalal M. N. Sarma	On the Complexity of Matroid Isomorphism Problem.	Theory Comput. Syst.	2011	DBLP DOI BibTeX RDF
1	Johannes Rauh, Thomas Kahle, Nihat Ay	Support sets in exponential families and oriented matroid theory.	Int. J. Approx. Reasoning	2011	DBLP DOI BibTeX RDF
1	Arne Bang Huseby	Oriented matroid systems.	Discrete Applied Mathematics	2011	DBLP DOI BibTeX RDF
1	André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, Guido Schäfer	Budgeted matching and budgeted matroid intersection via the gasoline puzzle.	Math. Program.	2011	DBLP DOI BibTeX RDF
1	Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák	Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
1	Maximilien Gadouleau, Alban Goupil	A Matroid Framework for Noncoherent Random Network Communications.	IEEE Transactions on Information Theory	2011	DBLP DOI BibTeX RDF
1	Shayan Oveis Gharan, Jan Vondrák	On Variants of the Matroid Secretary Problem.	ESA	2011	DBLP DOI BibTeX RDF
1	Monika Henzinger, Angelina Vidali	Multi-parameter Mechanism Design under Budget and Matroid Constraints.	ESA	2011	DBLP DOI BibTeX RDF
1	Ho Yee Cheung, Lap Chi Lau, Kai Man Leung	Algebraic Algorithms for Linear Matroid Parity Problems.	SODA	2011	DBLP BibTeX RDF
1	Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha	The Matroid Median Problem.	SODA	2011	DBLP BibTeX RDF
1	Sungjin Im, Yajun Wang	Secretary Problems: Laminar Matroid and Interval Scheduling.	SODA	2011	DBLP BibTeX RDF
1	Chandra Chekuri, Jan Vondrák, Rico Zenklusen	Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.	SODA	2011	DBLP BibTeX RDF
1	José A. Soto	Matroid Secretary Problem in the Random Assignment Model.	SODA	2011	DBLP BibTeX RDF
1	Leslie Ann Goldberg, Mark Jerrum	A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid.	ICALP	2011	DBLP DOI BibTeX RDF
1	Ashwinkumar Badanidiyuru Varadaraja	Buyback Problem - Approximate Matroid Intersection with Cancellation Costs.	ICALP	2011	DBLP DOI BibTeX RDF
1	Ilie Talpasanu, Shankar Krishnan	Exoskeleton systems kinematics analysis with graph-matroid approach.	CASE	2011	DBLP DOI BibTeX RDF
1	Asaf Cohen, Shlomi Dolev, Guy Leshem	Sensor Fusion: From Dependence Analysis via Matroid Bases to Online Synthesis.	ALGOSENSORS	2011	DBLP DOI BibTeX RDF
1	William Zhu, Shiping Wang	Rough matroid.	GrC	2011	DBLP DOI BibTeX RDF