检索结果-内蒙古大学图书馆

Hybrid 2D/3D photonic integration for non-planar circuit topologies

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Nesic, Aleksandar Blaicher, Matthias Hoose, Tobias Hofmann, Andreas Lauermann, Matthias Kutuvantavida, Yasar Nöllenburg, Martin Randel, Sebastian Freude, Wolfgang Koos, Christian Engesserstrasse 5 Karlsruhe76131 Germany Hermann-vonHelmholtz-Platz 1 Eggenstein-Leopoldshafen76344 Germany Hermann-von-Helmholtz-Platz 1 Eggenstein-Leopoldshafen76344 Germany Vanguard Photonics GmbH Gablonzer Strasse 10 Karlsruhe76185 Germany TU Wien Institute of Logic and Computation Algorithms and Complexity Group Favoritenstrasse 9-11 Vienna1040 Austria

Complex photonic integrated circuits (PIC) may have strongly non-planar topologies that require waveguide crossings (WGX) when realized in single-layer integration platforms. The number of WGX increases rapidly with the complexity of the circuit, in particular when it comes to highly interconnected optical switch topologies. Here, we present a concept for WGX-free PIC that rely on 3D-printed freeform waveguide overpasses (WOP). We experimentally demonstrate the viability of our approach using the example of a 4 × 4 switch-and-select (SAS) circuit realized on the silicon photonic platform. We further present a comprehensive graph-theoretical analysis of different n × n SAS circuit topologies. We find that for increasing port counts n of the SAS circuit, the number of WGX increases with n4, whereas the number of WOP increases only in proportion to n2. Copyright © 2019, The Authors. All rights reserved.

关键词： Timing circuits

Revisiting the hamiltonian theme in the square of a block: The general case

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Fleischner, Herbert Chia, Gek L. Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Austria Department of Mathematical and Actuarial Sciences Lee Kong Chian Faculty of Engineering and Science Universiti Tunku Abdul Rahman Sungai Long Campus Jalan Sungai Long Bandar Sungai Long Cheras KajangSelangor43000 Malaysia Institute of Mathematical Sciences University of Malaya Kuala Lumpur50603 Malaysia

This is the second part of joint research in which we show that every 2-connected graph G has the F4 property. That is, given distinct xi ∈ V (G), 1 ≤ i ≤ 4, there is an x1x2-hamiltonian path in G2 containing different edges x3y3, x4y4 ∈ E(G) for some y3, y4 ∈ V (G). However, it was shown already in [3, Theorem 2] that 2-connected DT-graphs have the F4 property;based on this result we generalize it to arbitrary 2-connected graphs. We also show that these results are best possible. Copyright © 2018, The Authors. All rights reserved.

关键词： Hamiltonians

On Erdős–Szekeres-type problems for k-convex point sets

学校读者我要写书评

暂无评论

European Journal of Combinatorics 2020年 89卷 103157-103157页

作者： Balko, Martin Bhore, Sujoy Martínez-Sandoval, Leonardo Valtr, Pavel Department of Applied Mathematics Charles University Prague Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria Institut de Mathématiques de Jussieu – Paris Rive Gauche (UMR 7586) Sorbonne Université Paris France Faculty of Sciences National Autonomous University of Mexico Mexico City Mexico

We study Erdős–Szekeres-type problems for k-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set S of n points is k-convex if there exists a spanning simple polygonization of S such that the intersection of any straight line with its interior consists of at most k connected components. We address several open problems about k-convex point sets. In particular, we extend the well-known Erdős–Szekeres Theorem by showing that, for every fixed k∈N, every set of n points in the plane in general position (with no three collinear points) contains a k-convex subset of size at least Ω(log^kn). We also show that there are arbitrarily large 3-convex sets of n points in the plane in general position whose largest 1-convex subset has size O(logn). This gives a solution to a problem posed by Aichholzer et al. (2014). We prove that there is a constant c>0 such that, for every n∈N, there is a set S of n points in the plane in general position such that every 2-convex polygon spanned by at least c⋅logn points from S contains a point of S in its interior. This matches an earlier upper bound by Aichholzer et al. (2014) up to a multiplicative constant and answers another of their open problems. © 2020 Elsevier Ltd

关键词：

Teleportation of quantum coherence

学校读者我要写书评

暂无评论

Physical Review A 2023年第4期108卷 042620-042620页

作者： Sohail Arun K. Pati Vijeth Aradhya Indranil Chakrabarty Subhasree Patro Quantum Information and Computation Group Harish-Chandra Research Institute A CI of Homi Bhabha National Institute Chhatnag Road Jhunsi Prayagraj 211019 India Centre for Quantum Science and Technology International Institute of Information Technology Hyderabad Gachibowli Hyderabad-500032 Telangana India Center for Security Theory and Algorithmic Research International Institute of Information Technology Hyderabad Gachibowli Hyderabad-500032 Telangana India Department of Computer Science National University of Singapore 117417 Singapore Computer science and physics department Utrecht University 3584 CS Utrecht The Netherlands Algorithms and complexity group QuSoft Centrum Wiskunde and Informatica 1098XG Amsterdam The Netherlands

We investigate whether it is possible to teleport the coherence of an unknown quantum state from Alice to Bob by communicating a smaller number of classical bits in comparison to what is required for teleporting an unknown quantum state. We find that we cannot achieve perfect teleportation of coherence with one bit of classical communication for an arbitrary qubit. However, we find that if the qubit is partially known, i.e., chosen from the equatorial and polar circles of the Bloch sphere, then teleportation of coherence is possible with the transfer of one cbit of information when we have maximally entangled states as a shared resource. In the case of the resource being a nonmaximally entangled state, we can teleport the coherence with a certain probability of success. In a general teleportation protocol for coherence, we derive a compact formula for the final state at Bob's laboratory in terms of the composition of the completely positive maps corresponding to the shared resource state and a joint positive operator-valued measure (POVM) performed by Alice on her qubit and the unknown state. Using this formula, we show that teleportation of the coherence of a partially known state with real matrix elements is perfectly possible with the help of a maximally entangled state as a resource. Furthermore, we explore the teleportation of coherence with Werner states and show that even when Werner states become separable, the amount of teleported coherence is nonzero, implying the possibility of teleportation of coherence without entanglement.

关键词： Quantum coherence & coherence measures Quantum communication Quantum correlations in quantum information Quantum information theory Quantum protocols

A study of 4−cycle systems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bagheri, B.Gh. Khosravi, M. Mahmoodian, E.S. Rashidi, S. Algorithms and Complexity Group Vienna University of Technology Favoritenstrasse 9-11 Vienna1040 Austria Department of Pure Mathematics Faculty of Mathematics and Computer Shahid Bahonar University of Kerman Kerman Iran Department of Mathematical Sciences Sharif University of Technology P.O. Box 11155-9415 Tehran Iran Department of Applied Mathematics Faculty of Mathematics and Computer Shahid Bahonar University of Kerman Kerman Iran

A 4−cycle system is a partition of the edges of the complete graph Kn into 4−cycles. Let C be a collection of cycles of length 4 whose edges partition the edges of Kn. A set of 4-cycles T1 ⊂ C is called a 4-cycle trade if there exists a set T2 of edge-disjoint 4-cycles on the same vertices, such that (C \ T1) ∪ T2 also is a collection of cycles of length 4 whose edges partition the edges of Kn. We study 4−cycle trades of volume two (double-diamonds) and three and show that the set of all 4-CS(9) is connected with respect of trading with trades of volume 2 (double-diamond) and 3. In addition, we present a full rank matrix whose null-space is containing *** Codes 05B30, 05B05 © 2023, CC BY-NC-ND.

关键词： Diamonds

complexity of Maker-Breaker Games on Edge Sets of Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Duchêne, Eric Gledel, Valentin Inerney, Fionn Mc Nisse, Nicolas Oijid, Nacim Parreau, Aline Stojaković, Miloš Univ Lyon CNRS INSA Lyon UCBL Centrale Lyon Univ Lyon 2 LIRIS UMR5205 VilleurbanneF-69622 France Université Savoie Mont Blanc CNRS LAMA ChambéryF-73000 France Algorithms and Complexity Group TU Wien Austria Université Côte d’Azur Inria CNRS I3S France Department of Mathematics and Informatics Faculty of Sciences University of Novi Sad Novi Sad Serbia

We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the H-game. Maker wins if she claims the edges of a perfect matching in the first, and a copy of a fixed graph H in the second. We prove that deciding who wins the perfect matching game and the H-game is PSPACE-complete, even for the latter in small-diameter graphs if H is a tree. Toward finding the smallest graph H for which the H-game is PSPACE-complete, we also prove that such an H of order 51 and size 57 exists. We then give several positive results for the H-game. As the H-game is already PSPACE-complete when H is a tree, we mainly consider the case where H belongs to a subclass of trees. In particular, we design two linear-time algorithms, both based on structural characterizations, to decide the winners of the P4-game in general graphs and the K1,-game in trees. Then, we prove that the K1,-game in any graph, and the H-game in trees are both FPT parameterized by the length of the game, notably adding to the short list of games with this property, which is of independent interest. Another natural direction to take is to consider the H-game when H is a cycle. While we were unable to resolve this case, we prove that the related arboricity-k game is polynomial-time solvable. In particular, when k = 2, Maker wins this game if she claims the edges of any *** Codes 91A24, 91A43, 91A46 © 2023, CC BY.

关键词： Trees (mathematics)

Tight complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

学校读者我要写书评

暂无评论

ACM Transactions on algorithms 1000年

作者： Jacob Focke Dániel Marx Fionn Mc Inerney Daniel Neuen Govind S. Sankar Philipp Schepper Philip Wellnitz CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria Max Planck Institute for Informatics Saarland Informatics Campus Germany Duke University US National Institute of Informatics and The Graduate University for Advanced Studies SOKENDAI Japan

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\)-set of a graph \(G\) is a set \(S\) of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\), and \(|N(v)\cap S|\in\rho\) for every \(v\not\in S\). The problem of finding a \((\sigma,\rho)\)-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many *** all pairs of finite or cofinite sets \((\sigma,\rho)\), we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\)-sets in time \(c_{\sigma,\rho}^{\rm{tw}} \cdot n^{O(1)}\) (if a tree decomposition of width \(\rm{tw}\) is given in the input). Let \(s_{\rm{top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{\rm{top}}\) is defined analogously for \(\rho\). Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{\rm{top}}+r_{\rm{top}}+2\) achieved by existing algorithms [van Rooij, 2020]. Toward defining \(c_{\sigma,\rho}\), we say that \((\sigma,\rho)\) is m-structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod m, and every integer in \(\rho\) equals \(\beta\) mod m. Then, setting—\(c_{\sigma,\rho}=s_{\rm{top}}+r_{\rm{top}}+2\) if \((\sigma,\rho)\) is not m-structured for any \(\rm{m}\geq 2\),—\(c_{\sigma,\rho}=\max\{s_{\rm{top}},r_{\rm{top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \(\rm{m}\)-structured for any \(\rm{m}\geq 3\), and \(s_{\rm{top}}=r_{\rm{top}}\) is even, and—\(c_{\sigma,\rho}=\max\{s_{\rm{top}},r_{\rm{top}}\}+1\), otherwise,we provide algorithms counting \((\sigma,\rho)\)-sets in time \(c_{\sigma,\rho}^{\rm{tw}}\cdot n^{O(1)}\). For e

关键词： dominating set independent set parameterized algorithms treewidth

Tight complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results

学校读者我要写书评

暂无评论

ACM Transactions on Computation Theory 1000年

作者： Jacob Focke Dániel Marx Fionn Mc Inerney Daniel Neuen Govind S. Sankar Philipp Schepper Philip Wellnitz CISPA Helmholtz Center for Information Security Saarbrucken Germany CISPA Helmholtz Center for Information Security Saarbrucken Germany Algorithms and Complexity Group TU Wien Vienna Austria Max Planck Institute for Informatics Saarland Informatics Campus Saarbrucken Germany Duke University Durham United States National Institute of Informatics Tokyo Japan The Graduate University for Advanced Studies Tokyo Japan

For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u)∩S| ∈ σ for every u ∈ S, and |N(v)∩S| ∈ ρ for every \(v\not\in S\). The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set, Dominating Set, Independent Dominating Set, and many *** an accompanying paper, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time \((c_{\sigma,\rho })^{\sf tw}\cdot n^{{\rm O}(1)}\) (if a tree decomposition of width \({\sf tw}\) is given in the input). Here, cσ, ρ is a constant with an intricate dependency on σ and ρ. Despite this intricacy, we show that the algorithms in the accompanying paper are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a \((c_{\sigma,\rho }-\varepsilon)^{\sf tw}\cdot n^{{\rm O}(1)}\)-algorithm counting the number of (σ, ρ)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well.

关键词： Dominating Set Independent Set Parameterized algorithms

Space-Efficient Parameterized algorithms on Graphs of Low Shrubdepth

学校读者我要写书评

暂无评论

ACM Transactions on Computation Theory 1000年

作者： Benjamin Bergougnoux Vera Chekan Robert Ganian Mamadou Moustapha Kanté Matthias Mnich Sang-il Oum Michał Pilipczuk Erik Jan van Leeuwen Institute of Informatics University of Warsaw Warsaw Poland Aix-Marseille Université CNRS LIS Marseille France Humboldt-Universitat zu Berlin Berlin Germany Algorithms and Complexity Group TU Wien Wien Austria Université Clermont Auvergne Clermont Auvergne INP CNRS Clermont-Ferrand France Hamburg University of Technology Hamburg Germany Discrete Mathematics Group Institute for Basic Science (IBS) Daejeon Korea (the Republic of) Institute of Informatics University of Warsaw Warsaw Poland Utrecht University Utrecht Netherlands

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms that achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width *** by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels,•Independent Set and Dominating Set can be solved in time \(2^{\mathcal {O}(dk)}\cdot n^{\mathcal {O}(1)}\) using \(\mathcal {O}(dk\log n)\) space;•Max Cut can be solved in time \(n^{\mathcal {O}(dk)}\) using \(\mathcal {O}(dk\log n)\) *** also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.

关键词： parameterized complexity shrubdepth space complexity algebraic methods