Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Recognizing interval bigraphs by forbidden patterns
View through CrossRef
AbstractLet be a connected bipartite graph with vertices and edges. We give an time algorithm to decide whether is an interval bigraph. The best known algorithm has time complexity and it was developed by Muller in 1997. Our approach is based on an ordering characterization of interval bigraphs introduced by Hell and Huang in 2003. We transform the problem of finding the desired ordering to choosing strong components of a pair‐digraph without creating conflicts. We make use of the structure of the pair‐digraph as well as decomposition of bigraph based on the special components of the pair‐digraph. This way we make explicit what the difficult cases are and gain efficiency by isolating such situations.
Title: Recognizing interval bigraphs by forbidden patterns
Description:
AbstractLet be a connected bipartite graph with vertices and edges.
We give an time algorithm to decide whether is an interval bigraph.
The best known algorithm has time complexity and it was developed by Muller in 1997.
Our approach is based on an ordering characterization of interval bigraphs introduced by Hell and Huang in 2003.
We transform the problem of finding the desired ordering to choosing strong components of a pair‐digraph without creating conflicts.
We make use of the structure of the pair‐digraph as well as decomposition of bigraph based on the special components of the pair‐digraph.
This way we make explicit what the difficult cases are and gain efficiency by isolating such situations.
Related Results
The epidemiology, radiology and biological characteristics of interval breast cancers in population mammography screening
The epidemiology, radiology and biological characteristics of interval breast cancers in population mammography screening
AbstractAn interval breast cancer is a cancer that emerges following a negative mammographic screen. This overview describes the epidemiology, and the radiological and biological c...
Regression analysis of interval-censored failure time data with non proportional hazards models
Regression analysis of interval-censored failure time data with non proportional hazards models
[ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT AUTHOR'S REQUEST.] Interval-censored failure time data arises when the failure time of interest is known only to lie within an i...
The Forbidden City in view - The photographic activity of foreign photographers of the Late Qing Dynasty in China
The Forbidden City in view - The photographic activity of foreign photographers of the Late Qing Dynasty in China
The article examines the photographic activity of foreign photographers during the late Qing Dynasty in China and analyzes their work in the context of historical material. The aut...
GW24-e3725 Tp-Te interval in Patients with Acute Hemorrhagic Stroke
GW24-e3725 Tp-Te interval in Patients with Acute Hemorrhagic Stroke
Objectives
To compare Tp-Te interval and Tp-Te/√R-R in patients with acute hemorrhagic stroke and healthy controls, examine the relationship of the parameters wit...
Decision to Delivery Interval, Perinatal Outcome and Factors Following Emergency Cesarean Section in Southern Ethiopia
Decision to Delivery Interval, Perinatal Outcome and Factors Following Emergency Cesarean Section in Southern Ethiopia
BACKGROUND: The interval between the decision for an emergency cesarean section and the delivery of the fetus should be made within 30 minutes. In a setting like Ethiopia, the reco...
Effects of grazing interval on basal cover of four perennial grasses in a summer-dry environment
Effects of grazing interval on basal cover of four perennial grasses in a summer-dry environment
The response to variation in grazing interval
over the spring–autumn period in southern New South Wales was examined
on 4 perennial grass species over 2 years. Plots of phalaris
(P...
Optimum birth interval (36–48 months) may reduce the risk of undernutrition in children: A meta-analysis
Optimum birth interval (36–48 months) may reduce the risk of undernutrition in children: A meta-analysis
BackgroundAlthough some studies have highlighted short birth interval as a risk factor for adverse child nutrition outcomes, the question of whether and to what extent long birth i...
Sibling Incest in Tabitha Suzuma’s Forbidden and Kate Avelynn’s Flawed
Sibling Incest in Tabitha Suzuma’s Forbidden and Kate Avelynn’s Flawed
This study purposely appoints the topic of sibling incest as reacted from the phenomenon of proliferation of illicit relationships that are increasingly being shown blatantly espec...