Search results for "perfect matching"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Stavros D. Nikolopoulos, Leonidas Palios	Maximum-Size Subgraphs of P4-Sparse Graphs Admitting a Perfect Matching.	Panhellenic Conference on Informatics	2005	DBLP DOI BibTeX RDF	P4-sparse graphs, maximum-size subgraphs, perfect matching, maximum matchings, Perfect graphs, cographs
3	Zhenhong Liu, Jianzhong Zhang 0001	On Inverse Problems of Optimum Perfect Matching.	J. Comb. Optim.	2003	DBLP DOI BibTeX RDF	maximum-mean alternating cycle, ellipsoid method, linear programming, perfect matching, strongly polynomial algorithm, maximum-weight matching
2	Marek Karpinski, Andrzej Rucinski, Edyta Szymanska	The Complexity of Perfect Matching Problems on Dense Hypergraphs.	ISAAC	2009	DBLP DOI BibTeX RDF
2	Carmela Troncoso, Benedikt Gierlichs, Bart Preneel, Ingrid Verbauwhede	Perfect Matching Disclosure Attacks.	Privacy Enhancing Technologies	2008	DBLP DOI BibTeX RDF
2	Bruno Escoffier, Jérôme Monnot, Olivier Spanjaard	Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality.	SOFSEM	2008	DBLP DOI BibTeX RDF	Bipartite perfect matching, Shortest path, Spanning tree, Robust optimization, Interval data
2	Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf	The Polynomially Bounded Perfect Matching Problem Is in NC 2.	STACS	2007	DBLP DOI BibTeX RDF
2	Yunting Lu, Dingjun Lou	An Algorithm to Solve the Partition into Perfect Matchings Problem in Halin Graphs.	International Conference on Computational Science	2007	DBLP DOI BibTeX RDF	Halin Graph, Algorithm, Perfect matching
2	Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf	On the Bipartite Unique Perfect Matching Problem.	ICALP	2006	DBLP DOI BibTeX RDF
2	Raghav Kulkarni	A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small.	CIAC	2006	DBLP DOI BibTeX RDF
2	Choudhury A. Al Sayeed, Ashraf Matrawy	Guaranteed Maximal Matching for Input Buffered Crossbar Switches.	CNSR	2006	DBLP DOI BibTeX RDF	Guaranteed maximal matching, iSLIP, MWM, scheduling, perfect matching, crossbar switches
2	Jérôme Monnot	On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems.	ISAAC	2005	DBLP DOI BibTeX RDF	labeled matching, approximate algorithms, NP-complete, bipartite graphs, colored matching
2	Heping Zhang	Regular Coronoids and Ear Decompositions of Plane Elementary Bipartite Graphs.	CJCDGCGT	2005	DBLP DOI BibTeX RDF	Regular coronoid, normal coronoid, plane elementary bipartite graph, regular decomposition, perfect matching, ear decomposition
2	Stefan Porschen	Solving Minimum Weight Exact Satisfiability in Time O(20.2441n).	ISAAC	2005	DBLP DOI BibTeX RDF	minimum weight exact satisfiability, branching tree, minimum perfect matching, NP-completeness, exact algorithm
2	Stefan Porschen, Bert Randerath, Ewald Speckenmeyer	Exact 3-satisfiability is decidable in time O(20.16254n).	Ann. Math. Artif. Intell.	2005	DBLP DOI BibTeX RDF	exact satisfiability, autonomous clause pattern, formula graph, NP-completeness, perfect matching
2	Michael E. Houle, Ferran Hurtado, Marc Noy, Eduardo Rivera-Campo	Graphs of Triangulations and Perfect Matchings.	Graphs and Combinatorics	2005	DBLP DOI BibTeX RDF	Non-crossing, Triangulation, Perfect matching
2	Elena Fernández, Oscar Meza	Even Cycles and Perfect Matching Problems with Side Constraints.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	even cycles, valid inequalities, matching problems
2	Ashok Kumar Ponnuswami, H. Venkateswaran	Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching Require Exponential Size.	FSTTCS	2004	DBLP DOI BibTeX RDF
2	Jacek Blazewicz, Piotr Formanowicz, Marta Kasprzak, Petra Schuurman, Gerhard J. Woeginger	DNA Sequencing, Eulerian Graphs, and the Exact Perfect Matching Problem.	WG	2002	DBLP DOI BibTeX RDF	computational complexity, graph theory, computational biology, DNA computing, DNA sequencing
2	Alexander A. Razborov	Resolution Lower Bounds for Perfect Matching Principles. (PDF / PS)	IEEE Conference on Computational Complexity	2002	DBLP DOI BibTeX RDF	Matching Principles, Resolution, Proof Complexity, Pigeonhole principle
2	Takeaki Uno	A Fast Algorithm for Enumerating Bipartite Perfect Matchings.	ISAAC	2001	DBLP DOI BibTeX RDF	enumeration, perfect matching, enumerating algorithm
2	Jianer Chen, Iyad A. Kanj	On Approximating Minimum Vertex Cover for Graphs with Perfect Matching.	ISAAC	2000	DBLP DOI BibTeX RDF
2	Kasturi R. Varadarajan	A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane.	FOCS	1998	DBLP DOI BibTeX RDF	algorithms, computational geometry, matching
2	Ran Raz, Avi Wigderson	Monotone Circuits for Matching Require Linear Depth.	J. ACM	1992	DBLP DOI BibTeX RDF	circuit depth, monotone computation, perfect matching
2	Michael D. Grigoriadis, B. Kalantari	A new class of heuristic algorithms for weighted perfect matching.	J. ACM	1988	DBLP DOI BibTeX RDF
2	Dexter Kozen, Umesh V. Vazirani, Vijay V. Vazirani	NC Algorithms for Comparability Graphs, Interval Gaphs, and Testing for Unique Perfect Matching.	FSTTCS	1985	DBLP DOI BibTeX RDF
1	Mathieu Lacroix, Ali Ridha Mahjoub, Sébastien Martin, Christophe Picouleau	On the NP-completeness of the perfect matching free subgraph problem.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
1	Ruth Haas, Michael Young	The anti-Ramsey number of perfect matching.	Discrete Mathematics	2012	DBLP DOI BibTeX RDF
1	Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran	Space complexity of perfect matching in bounded genus bipartite graphs.	J. Comput. Syst. Sci.	2012	DBLP DOI BibTeX RDF
1	Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf	Planarizing Gadgets for Perfect Matching do not Exist.	Electronic Colloquium on Computational Complexity (ECCC)	2011	DBLP BibTeX RDF
1	Deepak Bal, Andrzej Dudek, Zelealem Yilma	On the maximum number of edges in a hypergraph with a unique perfect matching.	Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Imdadullah Khan	Perfect matching in 3 uniform hypergraphs with large vertex degree	CoRR	2011	DBLP BibTeX RDF
1	Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. Variyam Vinodchandran	Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs.	STACS	2011	DBLP DOI BibTeX RDF
1	Yunlian Jiang, Kai Tian, Xipeng Shen, Jinghe Zhang, Jie Chen 0010, Rahul Tripathi	The Complexity of Optimal Job Co-Scheduling on Chip Multiprocessors and Heuristics-Based Solutions.	IEEE Trans. Parallel Distrib. Syst.	2011	DBLP DOI BibTeX RDF	CMP scheduling, cache contention, integer programming, perfect matching, shared cache, Co-scheduling
1	Samir Datta, Raghav Kulkarni, Raghunath Tewari	Perfect Matching in Bipartite Planar Graphs is in UL.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran	Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Marek Karpinski, Andrzej Rucinski, Edyta Szymanska	Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density.	Int. J. Found. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Nic Schraudolph	Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching.	Journal of Machine Learning Research - Proceedings Track	2010	DBLP BibTeX RDF
1	Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran	Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs	CoRR	2010	DBLP BibTeX RDF
1	Samir Datta, Raghav Kulkarni, Sambuddha Roy	Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs.	Theory Comput. Syst.	2010	DBLP BibTeX RDF
1	Krzysztof Diks, Piotr Stanczyk	Perfect Matching for Biconnected Cubic Graphs in O(n log2n) Time.	SOFSEM	2010	DBLP DOI BibTeX RDF
1	Hong Bian, Fuji Zhang	The graph of perfect matching polytope and an extreme problem.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Jean-Luc Fouquet, Jean-Marie Vanherpe	On the perfect matching index of bridgeless cubic graphs	CoRR	2009	DBLP BibTeX RDF
1	Kamalika Chaudhuri, Constantinos Daskalakis, Robert D. Kleinberg, Henry Lin	Online Bipartite Perfect Matching With Augmentations.	INFOCOM	2009	DBLP DOI BibTeX RDF
1	Kai Tian, Yunlian Jiang, Xipeng Shen	A study on optimally co-scheduling jobs of different lengths on chip multiprocessors.	Conf. Computing Frontiers	2009	DBLP DOI BibTeX RDF	cache contention, cmp scheduling, perfect matching, a*-search, co-scheduling
1	Noga Alon, Eyal Lubetzky, Ori Gurel-Gurevich	Choice-Memory Tradeoff in Allocations.	FOCS	2009	DBLP DOI BibTeX RDF	Space / performance tradeoffs, Lower bounds on memory, Balanced allocations, Online perfect matching, Balls and bins paradigm
1	Ashish Goel, Michael Kapralov, Sanjeev Khanna	Perfect matchings via uniform sampling in regular bipartite graphs.	SODA	2009	DBLP DOI BibTeX RDF
1	J. Salez, D. Shah	Optimality of belief propagation for random assignment problem.	SODA	2009	DBLP DOI BibTeX RDF
1	MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami	MaxMin allocation via degree lower-bounded arborescences.	STOC	2009	DBLP DOI BibTeX RDF	approximation algorithms, linear programming, graphs, lift-and-project
1	Yuichi Yoshida, Masaki Yamamoto, Hiro Ito	An improved constant-time approximation algorithm for maximum~matchings.	STOC	2009	DBLP DOI BibTeX RDF	constant-time approximation algorithms, minimum vertex cover, property testing, maximum matching, minimum set cover
1	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam	Minimizing movement.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF	pebble placement, graphs, Motion planning, Euclidean plane
1	Chuan-Ching Sue	An Enhanced Universal N x N Fully Nonblocking Quantum Switch.	IEEE Trans. Computers	2009	DBLP DOI BibTeX RDF
1	Prasad Chebolu, Alan M. Frieze, Páll Melsted, Gregory B. Sorkin	Average-Case Analyses of Vickrey Costs.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF	VCG auction, Random Assignment Problem, shortest path, minimum spanning tree, random graph, Average-case analysis, MST
1	Yueping Li, Zhe Nie	A Note on n-Critical Bipartite Graphs and Its Application.	COCOA	2009	DBLP DOI BibTeX RDF	n-critical graph, Matching, assignment
1	Evaggelos Lappas, Stavros D. Nikolopoulos, Leonidas Palios	An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs.	IWOCA	2009	DBLP DOI BibTeX RDF	paired-domination, algorithms, complexity, domination, permutation graphs
1	Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai	Best-Order Streaming Model.	TAMC	2009	DBLP DOI BibTeX RDF
1	Bernardo M. Ábrego, Esther M. Arkin, Silvia Fernández-Merchant, Ferran Hurtado, Mikio Kano, Joseph S. B. Mitchell, Jorge Urrutia	Matching Points with Squares.	Discrete & Computational Geometry	2009	DBLP DOI BibTeX RDF	Matching, Discrete geometry, Hamiltonian, Delaunay
1	Gyula Pap	Weighted restricted 2-matching.	Math. Program.	2009	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05C70, 90C27
1	Jérôme Monnot	A note on the hardness results for the labeled perfect matching problems in bipartite graphs.	RAIRO - Operations Research	2008	DBLP DOI BibTeX RDF
1	Samir Datta, Raghav Kulkarni, Sambuddha Roy	Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs	CoRR	2008	DBLP BibTeX RDF
1	Samir Datta, Raghav Kulkarni, Sambuddha Roy	Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs.	STACS	2008	DBLP DOI BibTeX RDF
1	Yunlian Jiang, Xipeng Shen, Jie Chen 0010, Rahul Tripathi	Analysis and approximation of optimal co-scheduling on chip multiprocessors.	PACT	2008	DBLP DOI BibTeX RDF	CMP scheduling, cache contention, perfect matching, co-scheduling
1	Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum	A (de)constructive approach to program checking.	STOC	2008	DBLP DOI BibTeX RDF	program testing, program correcting, program checking
1	Piotr Sankowski	Algebraic Graph Algorithms.	MFCS	2008	DBLP DOI BibTeX RDF
1	Jacek Blazewicz, Piotr Formanowicz, Marta Kasprzak, Petra Schuurman, Gerhard J. Woeginger	A polynomial time equivalence between DNA sequencing and the exact perfect matching problem.	Discrete Optimization	2007	DBLP DOI BibTeX RDF
1	Laurent Lyaudet, Pascal Koiran, Uffe Flarup	On the expressive power of planar perfect matching and permanents of bounded treewidth matrices	CoRR	2007	DBLP BibTeX RDF
1	Uffe Flarup, Pascal Koiran, Laurent Lyaudet	On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices.	ISAAC	2007	DBLP DOI BibTeX RDF
1	Yueping Li, Dingjun Lou	Finding the ( n , k , 0)-Extendability in Bipartite Graphs and Its Application.	International Conference on Computational Science	2007	DBLP DOI BibTeX RDF	matching extendability, algorithms, perfect matching
1	Stefan Porschen, Ewald Speckenmeyer	Algorithms for Variable-Weighted 2-SAT and Dual Problems.	SAT	2007	DBLP DOI BibTeX RDF	weighted satisfiability, edge cover, graph factor, NP-hardness, optimization problem, perfect matching
1	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam	Minimizing movement.	SODA	2007	DBLP DOI BibTeX RDF
1	Elliot Anshelevich, Adriana Karagiozova	Terminal backup, 3D matching, and covering cubic graphs.	STOC	2007	DBLP DOI BibTeX RDF	simplex matching, terminal backup, polynomial time
1	Joachim Pouderoux, Salvatore Spinello	Global Contour Lines Reconstruction in Topographic Maps.	ICDAR	2007	DBLP DOI BibTeX RDF
1	Ville Saari, Saska Lindfors	Analysis of Common-Mode Induced Even-Order Distortion in a Pseudo-Differential gm-C Filter.	ISCAS	2007	DBLP DOI BibTeX RDF
1	Raphael Yuster	Almost Exact Matchings.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
1	Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan	Planarity, Determinants, Permanents, and (Unique) Matchings.	CSR	2007	DBLP DOI BibTeX RDF
1	Tobias Brüggemann, Johann Hurink, Tjark Vredeveld, Gerhard J. Woeginger	Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines.	WAOA	2007	DBLP DOI BibTeX RDF
1	Refael Hassin, Jérôme Monnot, Danny Segev	The Complexity of Bottleneck Labeled Graph Problems.	WG	2007	DBLP DOI BibTeX RDF
1	Paul Dorbec, Sylvain Gravier, Michael A. Henning	Paired-domination in generalized claw-free graphs.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Generalized claw-free graphs, Paired-domination, Bounds
1	Michael A. Henning	Graphs with large paired-domination number.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Paired-domination, Minimum degree two, Bounds
1	Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf	The polynomially bounded perfect matching problem is in NC^2.	Electronic Colloquium on Computational Complexity (ECCC)	2006	DBLP BibTeX RDF
1	Ou Jianping	Maximal Hosoya index and extremal acyclic molecular graphs without perfect matching.	Appl. Math. Lett.	2006	DBLP DOI BibTeX RDF
1	Richard A. Brualdi, Martin Loebl, Ondrej Pangrác	Perfect Matching Preservers.	Electr. J. Comb.	2006	DBLP BibTeX RDF
1	W. Paulsen	Best Odds for Finding a Perfect Matching in a Bipartite Graph.	Combinatorics, Probability & Computing	2006	DBLP DOI BibTeX RDF
1	Pablo Diaz-Gutierrez, Anusheel Bhushan, M. Gopi, Renato Pajarola	Single-strips for fast interactive rendering.	The Visual Computer	2006	DBLP DOI BibTeX RDF	Single-strip, Weighted perfect matching, Vertex cache, Hamiltonian cycle, Visibility culling
1	Mustafa Keskin	A Background Mismatch Calibration For Capacitive Digitial-To-Analog Converters RTERS.	AHS	2006	DBLP DOI BibTeX RDF
1	Donna He, Oliver W. W. Yang	A Heuristic Detection/Protection Algorithm on DWDM Layers.	CCECE	2006	DBLP DOI BibTeX RDF
1	Pablo Diaz-Gutierrez, David Eppstein, M. Gopi	Single Triangle Strip and Loop on Manifolds with Boundaries.	SIBGRAPI	2006	DBLP DOI BibTeX RDF
1	David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian	Necklaces, Convolutions, and X + Y.	ESA	2006	DBLP DOI BibTeX RDF
1	Jianguo Qian	Induced Matching Extendable Graph Powers.	Graphs and Combinatorics	2006	DBLP DOI BibTeX RDF	AMS Subject Classifications 05C70 (05C35)
1	Jérôme Monnot	The labeled perfect matching in bipartite graphs.	Inf. Process. Lett.	2005	DBLP DOI BibTeX RDF
1	Jianer Chen, Iyad A. Kanj	On approximating minimum vertex cover for graphs with perfect matching.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
1	Piotr Sankowski	Processor efficient parallel matching.	SPAA	2005	DBLP DOI BibTeX RDF	polynomial matrix determinant, processor efficient, parallel algorithms, randomized algorithms, perfect matching, RNC
1	Samir Khuller, Kwangil Lee, Mark A. Shayman	On Degree Constrained Shortest Paths.	ESA	2005	DBLP DOI BibTeX RDF
1	Chun-Cheng Lin, Hsu-Chun Yen	On Balloon Drawings of Rooted Trees.	Graph Drawing	2005	DBLP DOI BibTeX RDF
1	H. Bekker, E. P. Braad, Boris Goldengorin	Using Bipartite and Multidimensional Matching to Select the Roots of a System of Polynomial Equations.	ICCSA	2005	DBLP DOI BibTeX RDF	system of polynomial equations, combinatorial optimization, bipartite matching
1	Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking	Decision Making Based on Approximate and Smoothed Pareto Curves.	ISAAC	2005	DBLP DOI BibTeX RDF
1	Khaled M. Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan	Simultaneous Matchings.	ISAAC	2005	DBLP DOI BibTeX RDF
1	Endre Szemerédi, Andrzej Rucinski, Vojtech Rödl	The Generalization of Dirac's Theorem for Hypergraphs.	MFCS	2005	DBLP DOI BibTeX RDF
1	Justus Schwartz, Angelika Steger, Andreas Weißl	Fast Algorithms for Weighted Bipartite Matching.	WEA	2005	DBLP DOI BibTeX RDF
1	Nathan Linial, Eyal Rozenman	Random Lifts Of Graphs: Perfekt Matchings.	Combinatorica	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C80, 05C70
1	Noga Alon, Raphael Yuster	On a Hypergraph Matching Problem.	Graphs and Combinatorics	2005	DBLP DOI BibTeX RDF