Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Perfect matching

Publications associées (33)

On random subgraphs of Kneser and Schrijver graphs

Andrei Kupavskii

A Kneser graph KG(n,k) is a graph whose vertices are in oneto-one correspondence with k -element subsets of [n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lowisz states that the chromatic num ...

Academic Press Inc Elsevier Science2016

Analysis and Characterization of Variability in Subthreshold Source-Coupled Logic Circuits

Yusuf Leblebici, Alexandre Schmid, Mahsa Shoaran, Seyed Armin Tajalli

This article explores the effect of device parameter variations on the performance of subthreshold source-coupled logic (STSCL) circuits. A test chip has been fabricated in a standard CMOS 90 nm technology to study the matching properties of STSCL circuits ...

2015

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?

Matthias Grossglauser, Ehsan Kazemi, Lyudmila Yartseva

Network alignment refers to the problem of matching the vertex sets of two unlabeled graphs, which can be viewed as a generalization of the classic graph isomorphism problem. Network alignment has applications in several fields, including social network an ...

2015

Exponentiality of the exchange algorithm for finding another room-partitioning

Laura Sanità

Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange ...

Elsevier Science Bv2014

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...

IEEE2013

Detection sensitivity and light collection studies of an APD-based high packing-fraction LYSO:Ce matrix for PET applications

The ClearPEM is a dedicated APD-based PET detector for high-resolution breast cancer imaging. The detector module is composed of 12 LYSO:Ce crystal matrices, each with 4 x 8 individual crystals (2 x 2 x 20 mm(3)) optically coupled on both ends to S8550 Ham ...

Elsevier Science Bv2013

Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

Yuri Faenza, Hans Raj Tiwary

We show that the binary logarithm of the nonnegative rank of a nonnegative matrix is, up to small constants, equal to the minimum complexity of a randomized communication protocol computing the matrix in expectation. We use this connection to prove new con ...

Springer Berlin Heidelberg2012

Minimum d-blockers and d-transversals in graphs

Dominique de Werra

We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d el ...

2011

Computing correspondences in geometric data sets

Mark Pauly, Hao Li

Shape registration and, more generally speaking, computing correspondence across shapes are fundamental problems in computer graphics and vision. Problems from this area show up in many diff erent variants such as scan registration, deformable shape matchi ...

2011

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Dominique de Werra, Bernard Ries

Given an undirected graph G = (V, E) with matching number nu(G), a d-blocker is a subset of edges B such that nu((V, E \ B))

Elsevier2010

Robust, High-Speed Interest Point Matching for Real-Time Applications

Michael Calonder

A typical Computer Vision system needs to process vast amounts of data as captured by one or more cameras, constantly testing the capabilities of today's hardware. Yet such systems face an ever-growing computational load caused by the more and more demandi ...

EPFL2010

Blockers and transversals

Dominique de Werra, Bernard Ries

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

Elsevier2009

On the inapproximability of independent domination in 2P3-free perfect graphs

Dominique de Werra

We consider the complexity of approximation for the INDEPENDENT DOMINATING SET problem in 2P(3)-free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as all induced subgraph. We show that, if P not equal ...

2009