Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

MOSFET: Enhancement Mode01:22

MOSFET: Enhancement Mode

240
Enhancement-mode MOSFETs are pivotal components in electronics, distinguished by their capacity to act as highly efficient switches. They are part of the larger family of metal-oxide Semiconductor Field-Effect Transistors (MOSFETs). They are available in two types: p-channel and n-channel, each tailored to specific polarity operations.
In their basic form, enhancement-mode MOSFETs are typically non-conductive when the gate-source voltage (Vgs) is zero. This default 'off' state means no...
240

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same journal

Sum Index, Difference Index and Exclusive Sum Number of Graphs.

Graphs and combinatorics·2026
Same journal

Note on extremal problems about connected subgraph sums.

Graphs and combinatorics·2026
Same journal

Note on Polychromatic Coloring of Hereditary Hypergraph Families.

Graphs and combinatorics·2024
Same journal

Perfect <i>k</i>-Colored Matchings and <math><mrow><mo>(</mo> <mi>k</mi> <mo>+</mo> <mn>2</mn> <mo>)</mo></mrow></math> -Gonal Tilings.

Graphs and combinatorics·2020
Same journal

Disjoint Paired-Dominating sets in Cubic Graphs.

Graphs and combinatorics·2019

Related Experiment Video

Updated: May 10, 2025

Patterning of Embryonic Stem Cells Using the Bio Flip Chip
05:25

Patterning of Embryonic Stem Cells Using the Bio Flip Chip

Published on: October 1, 2007

9.4K

On Flipping Edge Sets in Unique Sink Orientations.

Michaela Borzechowski1, Simon Weber2

  • 1Freie Universität Berlin, Berlin, Germany.

Graphs and Combinatorics
|April 28, 2025
PubMed
Summary

Researchers developed a faster algorithm to compute phases for unique sink orientations (USOs) in hypercube graphs. This advancement improves computational efficiency for USO analysis and related graph theory problems.

Keywords:
PhaseReconfigurationUnique sink orientation

More Related Videos

One-Step Approach to Fabricating Polydimethylsiloxane Microfluidic Channels of Different Geometric Sections by Sequential Wet Etching Processes
08:31

One-Step Approach to Fabricating Polydimethylsiloxane Microfluidic Channels of Different Geometric Sections by Sequential Wet Etching Processes

Published on: September 13, 2018

9.7K
Reconfigurable Microfluidic Channel with Pin-discretized Sidewalls
10:39

Reconfigurable Microfluidic Channel with Pin-discretized Sidewalls

Published on: April 12, 2018

7.4K

Related Experiment Videos

Last Updated: May 10, 2025

Patterning of Embryonic Stem Cells Using the Bio Flip Chip
05:25

Patterning of Embryonic Stem Cells Using the Bio Flip Chip

Published on: October 1, 2007

9.4K
One-Step Approach to Fabricating Polydimethylsiloxane Microfluidic Channels of Different Geometric Sections by Sequential Wet Etching Processes
08:31

One-Step Approach to Fabricating Polydimethylsiloxane Microfluidic Channels of Different Geometric Sections by Sequential Wet Etching Processes

Published on: September 13, 2018

9.7K
Reconfigurable Microfluidic Channel with Pin-discretized Sidewalls
10:39

Reconfigurable Microfluidic Channel with Pin-discretized Sidewalls

Published on: April 12, 2018

7.4K

Area of Science:

  • Graph Theory
  • Combinatorics
  • Computational Geometry

Background:

  • Unique Sink Orientations (USOs) are fundamental in discrete geometry and graph theory, specifically concerning orientations of hypercube graphs.
  • The flip graph on USOs is a key structure, enabling transformations between different USO configurations.
  • Schurr's theorem provides a theoretical basis for understanding phase decomposition within USO edges along specific dimensions.

Purpose of the Study:

  • To develop an efficient algorithm for computing the phases of a given n-dimensional USO.
  • To analyze the space complexity of flipping phases within the USO flip graph.
  • To investigate the computational complexity of determining phase membership for USOs encoded via boolean circuits.

Main Methods:

  • Developed a novel algorithm to compute phases of a USO in O(n^2) time.
  • Analyzed space complexity, showing phase flipping requires only poly(n) additional space.
  • Established the co-NP-completeness of determining if two edges belong to the same phase for circuit-encoded USOs.

Main Results:

  • An O(n^2) algorithm for computing USO phases, a significant improvement over the previous O(n^3) trivial algorithm.
  • Demonstrated that flipping a phase requires only poly(n) auxiliary space.
  • Proved that deciding phase equivalence for circuit-encoded USOs is co-NP-complete.

Conclusions:

  • The new algorithm provides a substantial efficiency gain for USO phase computation.
  • The findings highlight a dichotomy between efficient phase manipulation and computationally hard phase determination for succinct USO representations.
  • Further research into the structural properties of USO phases is warranted.