Log in

Relevant bibliographies by topics / Minimum Weight Perfect Matching

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'Minimum Weight Perfect Matching'

Author: Grafiati

Published: 27 July 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Minimum Weight Perfect Matching.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Minimum Weight Perfect Matching"

1

Cook, William, and André Rohe. "Computing Minimum-Weight Perfect Matchings." INFORMS Journal on Computing 11, no. 2 (1999): 138–48. http://dx.doi.org/10.1287/ijoc.11.2.138.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Criger, Ben, and Imran Ashraf. "Multi-path Summation for Decoding 2D Topological Codes." Quantum 2 (October 19, 2018): 102. http://dx.doi.org/10.22331/q-2018-10-19-102.

Full text

Abstract:

Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance. To obtain high performance with these architectures, we require a decoder which can adapt to the wide variety of error models present in experiments. The typical approach to the problem of decoding the surface code is to reduce it to minimum-weight perfect matching in a way that provides a suboptimal threshold error rate, and is specialized to correct a specific error model. Recently, optimal threshold error rates for a variety of error models have been obtained by methods which do not use minimum-weight perfect matching, showing that such thresholds can be achieved in polynomial time. It is an open question whether these results can also be achieved by minimum-weight perfect matching. In this work, we use belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes. This allows us to correct depolarizing errors using the rotated surface code, obtaining a threshold of 17.76±0.02%. This is larger than the threshold achieved by previous matching-based decoders (14.88±0.02%), though still below the known upper bound of ∼18.9%.

APA, Harvard, Vancouver, ISO, and other styles

3

Delon, J., J. Salomon, and A. Sobolevski. "Minimum—weight perfect matching for nonintrinsic distances on the line." Journal of Mathematical Sciences 181, no. 6 (2012): 782–91. http://dx.doi.org/10.1007/s10958-012-0714-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

BIENKOWSKI, MARCIN, and PAWEŁ ZALEWSKI. "(1,2)-HAMILTONIAN COMPLETION ON A MATCHING." International Journal of Foundations of Computer Science 24, no. 01 (2013): 95–108. http://dx.doi.org/10.1142/s0129054113500019.

Full text

Abstract:

We consider the problem of computing a minimum-weight Hamiltonian cycle on an undirected graph with edges' weights from set {0, 1, 2}, where 0-weight edges create a perfect matching of the graph. We provide a (4/3)-approximation algorithm and show that the problem is APX-complete.

APA, Harvard, Vancouver, ISO, and other styles

5

Fowler, Austin G. "Minimum weight perfect matching of fault-tolerant topological quantum error correction in average O(1) parallel time." Quantum Information and Computation 15, no. 1&2 (2015): 145–58. http://dx.doi.org/10.26421/qic15.1-2-9.

Full text

Abstract:

Consider a 2-D square array of qubits of extent $L\times L$. We provide a proof that the minimum weight perfect matching problem associated with running a particular class of topological quantum error correction codes on this array can be exactly solved with a 2-D square array of classical computing devices, each of which is nominally associated with a fixed number $N$ of qubits, in constant average time per round of error detection independent of $L$ provided physical error rates are below fixed nonzero values, and other physically reasonable assumptions. This proof is applicable to the fully fault-tolerant case only, not the case of perfect stabilizer measurements.

APA, Harvard, Vancouver, ISO, and other styles

6

Huang, Siming, and Zhenhong Liu. "On the inverse problem of linear programming and its application to minimum weight perfect k-matching." European Journal of Operational Research 112, no. 2 (1999): 421–26. http://dx.doi.org/10.1016/s0377-2217(97)00444-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Osiakwan, Constantine K. N., and Selim G. Akl. "AnEPAlgorithm for Computing a Minimum Weight Perfect Matching for a Set of Points on the Plane." ORSA Journal on Computing 6, no. 4 (1994): 436–44. http://dx.doi.org/10.1287/ijoc.6.4.436.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Merino, Criel, Gelasio Salazar, and Jorge Urrutia. "On the Intersection Number of Matchings and Minimum Weight Perfect Matchings of Multicolored Point Sets." Graphs and Combinatorics 21, no. 3 (2005): 333–41. http://dx.doi.org/10.1007/s00373-004-0606-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Bogdanowicz, Damian, and Krzysztof Giaro. "On a matching distance between rooted phylogenetic trees." International Journal of Applied Mathematics and Computer Science 23, no. 3 (2013): 669–84. http://dx.doi.org/10.2478/amcs-2013-0050.

Full text

Abstract:

Abstract The Robinson-Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach based on a minimum-weight perfect matching in bipartite graphs, the values of similarity between clusters are transformed to the final MC-score of the dissimilarity of trees. The analyzed properties give insight into the structure of the metric space generated by MC, its relations with the Matching Split (MS) distance of unrooted trees and asymptotic behavior of the expected distance between binary n-leaf trees selected uniformly in both MC and MS (Θ(n3/2)).

APA, Harvard, Vancouver, ISO, and other styles

10

Imielińska, C., and B. Kalantari. "A General Class of Heuristics for Minimum Weight Perfect Matching and Fast Special Cases with Doubly and Triply Logarithmic Errors." Algorithmica 18, no. 4 (1997): 544–59. http://dx.doi.org/10.1007/pl00009172.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Minimum Weight Perfect Matching"

1

Corazza, Federico Augusto. "Analysis of graph-based quantum error-correcting codes." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/23801/.

Full text

Abstract:

With the advent of quantum computers, there has been a growing interest in the practicality of this device. Due to the delicate conditions that surround physical qubits, one could wonder whether any useful computation could be implemented on such devices. As we describe in this work, it is possible to exploit concepts from classical information theory and employ quantum error-correcting techniques. Thanks to the Threshold Theorem, if the error probability of physical qubits is below a given threshold, then the logical error probability corresponding to the encoded data qubit can be arbitrarily low. To this end, we describe decoherence which is the phenomenon that quantum bits are subject to and is the main source of errors in quantum memories. From the cause of error of a single qubit, we then introduce the error models that can be used to analyze quantum error-correcting codes as a whole. The main type of code that we studied comes from the family of topological codes and is called surface code. Of these codes, we consider both the toric and planar structures. We then introduce a variation of the standard planar surface code which better captures the symmetries of the code architecture. Once the main properties of surface codes have been discussed, we give an overview of the working principles of the algorithm used to decode this type of topological code: the minimum weight perfect matching. Finally, we show the performance of the surface codes that we introduced, comparing them based on their architecture and properties. These simulations have been performed with different error channel models to give a more thorough description of their performance in several situations showing relevant results.

APA, Harvard, Vancouver, ISO, and other styles

2

Liu, Yu-Chuan, and 劉育全. "Heuristics for the Minimum-Weight Perfect Matching Problem on a Plane." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/yzy98q.

Full text

Abstract:

碩士<br>國立臺灣大學<br>資訊工程學研究所<br>105<br>In this thesis, we provide some heuristic algorithms for minimum-weight perfect matching problem on a plane. First, we provide a local search algorithm based on triangle inequality. Then we try many methods to improve this algorithm. Finally we get some good algorithms. One can be 20-30 times faster than Blossom algorithm with 2% error and other one can be 3-4 times faster than Blossom algorithm with 0.5% error.

APA, Harvard, Vancouver, ISO, and other styles

3

(8708778), Steven Alec Gallagher. "A 4/3-approximation for Minimum Weight Edge Cover." Thesis, 2020.

Find full text

Abstract:

This paper addresses the minimum weight edge cover problem (MEC), which is stated as follows: Given a graph <i>G= (V,E)</i>, find a set of edges <i>S:S⊆E </i>and ∑<sub>e∈S</sub><sup>w(e) </sup></∑<sub>e∈Q<sup>w(e)</sup>∀Q: Q is an edge cover. Where an edge cover <i>P</i> is a set of edges such that ∀v∈V <i>v</i> is incident to at least one edge in <i>P</i>. An efficient implementation of a 4/3-approximation for MEC is provided. Empirical results obtained experimentally from practical data sets are reported and compared against various other approximation algorithms for MEC.<br>

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Minimum Weight Perfect Matching"

1

Holloway, N. W., S. Ravindran, and A. M. Gibbons. "Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality." In Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 1994. http://dx.doi.org/10.1007/3-540-57899-4_37.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Emek, Yuval, Yaacov Shapiro, and Yuyi Wang. "Minimum Cost Perfect Matching with Delays for Two Sources." In Lecture Notes in Computer Science. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-57586-5_18.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Mirzaian, Andy. "Minimum weight euclidean matching and weighted relative neighborhood graphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-57155-8_275.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Chen, Jianer, and Iyad A. Kanj. "On Approximating Minimum Vertex Cover for Graphs with Perfect Matching." In Algorithms and Computation. Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-40996-3_12.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Asathulla, Mudabir Kabir, Sanjeev Khanna, Nathaniel Lahn, and Sharath Raghvendra. "A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs." In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018. http://dx.doi.org/10.1137/1.9781611975031.31.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Mukhopadhyay, Premangshu, Goutam Kumar Bose, and Pritam Pain. "MCDM-Based Optimization of Performance Characteristics During µEDMing of SS 304." In Machine Learning Applications in Non-Conventional Machining Processes. IGI Global, 2021. http://dx.doi.org/10.4018/978-1-7998-3624-7.ch002.

Full text

Abstract:

Micro-EDM is most widely used for developing perfect drilled micro features/parts. Research was carried out to improve the material removal and tool wear of any conductive machined product by EDM and micro-EDM process. In this chapter, RSM was used for designing the experiments with 20 set of experiments. In this present research work, performance characteristics like MRR and Overcut have got a different level of importance. Here the stress was given on MRR rather than on OC. In this MCDM analysis, the weight of MRR is considered to be maximum (i.e., larger is better), and other weights of other responses are considered to be the minimum (i.e., smaller is better). Finally, in the midst of all the combinations of process parameters considered one that acquires the highest grey relational grade is the best parametric combination. The research findings in the area of machining of stainless steel 304 will be helpful to manufacturing engineers for selecting the optimized parametric combinations of micro-EDM process with stainless steel.

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Minimum Weight Perfect Matching"

1

Bogdanowicz, Damian. "Comparing phylogenetic trees using a minimum weight perfect matching." In 2008 1st International Conference on Information Technology (IT 2008). IEEE, 2008. http://dx.doi.org/10.1109/inftech.2008.4621680.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Songsiri, Patoomsiri, Thimaporn Phetkaew, Ryutaro Ichise, and Boonserm Kijsirikul. "Sub-classifier construction for error correcting output code using minimum weight perfect matching." In 2014 International Joint Conference on Neural Networks (IJCNN). IEEE, 2014. http://dx.doi.org/10.1109/ijcnn.2014.6889436.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Angadi, Shanmukhappa, and Vilas Naik. "Static video summarization - A minimum edge weight bipartite graph matching approach." In 2015 IEEE International Conference on Computer Graphics, Vision and Information Security (CGVIS). IEEE, 2015. http://dx.doi.org/10.1109/cgvis.2015.7449901.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Yuan, Tingting, Xiaohong Huang, Maode Ma, and Jie Yuan. "Balance-Based SDN Controller Placement and Assignment with Minimum Weight Matching." In 2018 IEEE International Conference on Communications (ICC 2018). IEEE, 2018. http://dx.doi.org/10.1109/icc.2018.8422637.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Oncan, T., and I. K. Altinel. "Iterated exact and heuristic algorithms for the minimum cost bipartite perfect matching problem with conflict constraints." In 2017 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, 2017. http://dx.doi.org/10.1109/ieem.2017.8290049.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Maity, Souvik, Soumik Dalal, Sayan Ranu, and Lelitha Vanajakshi. "A weight-based map matching algorithm using minimum input variables for urban road networks." In 2017 9th International Conference on Communication Systems and Networks (COMSNETS). IEEE, 2017. http://dx.doi.org/10.1109/comsnets.2017.7945429.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Cruz, Jadder Bismarck de Sousa, Cândida Nunes da Silva, and Orlando Lee. "Some Partial Results on Linial's Conjecture for Matching-Spine Digraphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16386.

Full text

Abstract:

Let $k$ be a positive integer. A \emph{partial $k$-coloring} of a digraph $D$ is a set $\calC$ of $k$ disjoint stable sets and has \emph{weight} defined as $\sum_{C \in \calC} |C|$. An \emph{optimal} $k$-coloring is a $k$-coloring of maximum weight. A \emph{path partition} of a digraph $D$ is a set $\calP$ of disjoint paths of $D$ that covers its vertex set and has \emph{$k$-norm} defined as $\sum_{P \in \mathcal{P}} \min\{|P|,k\}$. A path partition $\calP$ is \emph{$k$-optimal} if it has minimum $k$-norm. A digraph $D$ is \emph{matching-spine} if its vertex set can be partitioned into sets $X$ and $Y$, such that $D[X]$ has a Hamilton path and the arc set of $D[Y]$ is a matching. Linial (1981) conjectured that the $k$-norm of a $k$-optimal path partition of a digraph is at most the weight of an optimal partial $k$-coloring. We present some partial results on this conjecture for matching-spine digraphs.

APA, Harvard, Vancouver, ISO, and other styles

8

Zheng, Xinqian, and Heli Yang. "Influence of Tip Clearance on the Performance and Matching of Multistage Axial Compressors." In ASME Turbo Expo 2016: Turbomachinery Technical Conference and Exposition. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/gt2016-56232.

Full text

Abstract:

Tip clearance has great influence on the performance of multistage axial compressors including efficiency, pressure rise, mass flow, as well as matching. This paper reports a study into the influence of tip clearance on the performance and matching of a 5-stage axial compressor by a numerical method. Different tip clearances from 0% to 5.0% span which represents the typical range of tip clearance in modern multistage axial compressors were simulated and analyzed. The results show that as tip clearance increases from 0% to 5.0% span, the choked mass flow decreases by about 21.8%, the peak pressure ratio decreases by about 43.1% and the peak efficiency decreases about 14.3 percents. As tip clearance increases, the efficiency of the whole compressor decreases in a parabolic manner not linearly as previous suggested, which is partially attributable to the cantilevered stators considered in this paper and primarily due to the mismatching of different stages. It is of great importance to control the tip clearance. When tip clearance increases, the front stage tends to work near surge condition and the rear stage tends to work near choke condition, which leads to lower efficiency than in the middle stages. A weight was defined to evaluate each stage’s contribution to the whole compressor’s efficiency deficit caused by the increase of tip clearance. Front and rear stages contribute more to the efficiency deficit than the middle stages, which indicates that more attention should be paid on front and rear stages to improve the performance of multistage axial compressors. In order to evaluate the matching of multistage axial compressors with a quantified method, a new parameter named “Peak Efficiency Deviation (PED)” was defined based on the difference between each stage’s operating efficiency and its peak efficiency. The mass flow of multistage axial compressors should be well considered to make the PED parameter to be close to zero as possible. In the most commonly used range of tip clearance from 0.5% to 3.0% span, the PED varies little within 0.4 percent, which is only about 8.4% of the peak efficiency deficit at 1.5% span tip clearance. So, the PED could be small within a wide range of tip clearances if the matching of the compressor is perfect at design tip clearance.

APA, Harvard, Vancouver, ISO, and other styles

9

Zeng, Youjiao, Junqi Yan, Ye Jin, and Tao Jiang. "Optimization of Multiple Head SMT Placement Machine: Model and Approaches." In ASME 2002 International Mechanical Engineering Congress and Exposition. ASMEDC, 2002. http://dx.doi.org/10.1115/imece2002-39500.

Full text

Abstract:

In order to maximize the throughput rate of single multiple head surface mounted technology placement machine, the time taken for pick-and-place of components for each printed circuit board has to be minimized. This gives rise to two related essential problems, namely feeder assignment problem and pick-and-place sequence determination problem. In this paper, we introduce a model that simplifies problems. We regard all components during a pick-and-place cycle as a unit and give it a matching weight. In this way, we change multiple head machine problems into single head machine problems. The optimisation problem becomes two sub-problems: minimum weight matching problem and travelling salesman problem of these units. We presented algorithms to obtain near optimal solution and implement them as a computer program. We performed experiment on a real four head placement machine. The experimental results are presented to analyse their performance.

APA, Harvard, Vancouver, ISO, and other styles

10

Schulz, Martin, Fritz Klocke, Jan Riepe, Nils Klingbeil, and Kristian Arntz. "Process Optimization of Wire Based Laser Metal Deposition of Titanium." In ASME Turbo Expo 2018: Turbomachinery Technical Conference and Exposition. American Society of Mechanical Engineers, 2018. http://dx.doi.org/10.1115/gt2018-76924.

Full text

Abstract:

Titanium alloys are used instead of steel and nickel-based alloys to lower the weight of turbines whenever it is applicable. Due to the high manufacturing costs of titanium, near-net-shape processes like laser metal deposition (LMD) processes are an approach to improve the production of new turbomachinery components. Additionally, these processes are also suitable for repair. LMD uses wire or powder as additional material. When highly reactive materials like titanium grade 5 (Ti6Al4V) are processed, wire-based laser metal deposition (LMD-W) processes are superior to powder-based processes due to the smaller reactive surface. Nowadays, three main challenges exist when titanium grade 5 (Ti6Al4V) is processed by additive manufacturing (AM): First of all the high affinity to oxygen combined with the increased brittleness of the material in case of a contamination with already low amounts of oxygen has to be faced. Secondly, the material is prone to distortion induced by thermal stress during the manufacturing process. Finally, the material has a complex bimodal microstructure, which has to be adjusted properly to generate optimal strength. The following publication will present how these technical challenges are faced. A local shielding gas concept demonstrates how flooding of the process chamber was avoided. The distortion was lowered by minimizing the heat input. Therefore, the laser spot was adapted. Its size was reduced to physical minimum nearly matching the size of the wire. To avoid process aborts, the proper feeding of the wire was improved. With this optimized process, it was possible to generate several specimens for metallurgical analysis. Finally, treatments to modify the alpha-martensitic-structure into a bimodal structure were performed. Summarizing the results show that the LMD-W process was improved to overcome the main challenges. Thereby the process has become suitable for manufacturing turbomachinery components made from titanium grade 5.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!