Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Open Packing in Interval Graphs
View through CrossRef
Abstract
Total Domination and Open Packing forms a primal-dual pair of problems. A vertex subset S of a graph G is called an open packing in G if no pair of distinct vertices in S have a common neighbour in G. The cardinality of a maximum open packing in G is called the open packing number, ρᵒ(G), of G which is a lower bound for the total domination number of G. Given a graph G and a positive integer k, the problem OPEN PACKING tests whether G has an open packing of size at least k. It is known that OPEN PACKING is NP-complete for split graphs (and so for chordal graphs) [Ramos et al., 2014]. In this work, we use a dynamic programming based approach to show that a maximum open packing in interval graphs (a subclass of chordal graphs) can be found in O(n³) time.
Title: Open Packing in Interval Graphs
Description:
Abstract
Total Domination and Open Packing forms a primal-dual pair of problems.
A vertex subset S of a graph G is called an open packing in G if no pair of distinct vertices in S have a common neighbour in G.
The cardinality of a maximum open packing in G is called the open packing number, ρᵒ(G), of G which is a lower bound for the total domination number of G.
Given a graph G and a positive integer k, the problem OPEN PACKING tests whether G has an open packing of size at least k.
It is known that OPEN PACKING is NP-complete for split graphs (and so for chordal graphs) [Ramos et al.
, 2014].
In this work, we use a dynamic programming based approach to show that a maximum open packing in interval graphs (a subclass of chordal graphs) can be found in O(n³) time.
Related Results
Production Tubing Frac Pack: An Unconventional Multi-Zone Design with Significant Cost Savings
Production Tubing Frac Pack: An Unconventional Multi-Zone Design with Significant Cost Savings
Abstract
The conventional process of frac packing that was initiated in the early 1990s and revolutionized the industry is well documented in the literature (Meese, ...
Computing the Energy of Certain Graphs based on Vertex Status
Computing the Energy of Certain Graphs based on Vertex Status
Background:
The concept of Hückel molecular orbital theory is used to compute the graph energy numerically and graphically on the base of the status of a vertex.
Objective:
Our a...
Evaluation of Postoperative Practices Regarding Packing of the External Auditory Canal
Evaluation of Postoperative Practices Regarding Packing of the External Auditory Canal
BACKGROUND: Packing of the external auditory canal after ear surgery is an established practice in most otologic centers. However, no guidelines exist concerning the management of ...
Experimental and Visual Simulation of Gravel Packing in Horizontal and Highly Deviated Wells
Experimental and Visual Simulation of Gravel Packing in Horizontal and Highly Deviated Wells
Abstract
The gravel packing process in horizontal or highly deviated wells involves the solid-liquid two-phase flow and the sand-bed migration under complicated cond...
Cased Hole Gravel Packing Evaluation for Refining Production Enhancement Approach
Cased Hole Gravel Packing Evaluation for Refining Production Enhancement Approach
Abstract
Sand production and fines migration can cause numerous issues in poorly consolidated sand formations, such as eroding screens, filling the wellbore, and neg...
Full Ventricular Capture Indicated by the QT Interval Function
Full Ventricular Capture Indicated by the QT Interval Function
The atrioventricular (AV) interval is critical in dual chamber (DDD) pacing in patients with hypertrophic obstructive cardiomyopathy (HOCM) to obtain full ventricular capture (FVC)...
On Tuza's conjecture in even co-chain graphs
On Tuza's conjecture in even co-chain graphs
In 1981, Tuza conjectured that the cardinality of a minimum set of edges that intersects every triangle of a graph is at most twice the cardinality of a maximum set of edge-disjoin...
Design of Gravel Packs in Deviated Wellbores
Design of Gravel Packs in Deviated Wellbores
This paper describes a new technique for improving the effectiveness of gravel placement between the screen and the wellbore in deviated wells. This technique can be used to predic...