19 results
Search Results
2. Exploring q-Bernstein-Bézier surfaces in Minkowski space: Analysis, modeling, and applications.
- Author
-
Bashir, Sadia, Ahmad, Daud, and Ali, Ghada
- Subjects
MINKOWSKI space ,MICROSOFT Surface (Computer) ,COMPUTER graphics ,COMPUTER-aided design ,GEOMETRIC modeling ,GAUSSIAN curvature ,MATHEMATICS - Abstract
In this paper, we examine q-Bernstein-Bézier surfaces in Minkowski space- R13 with q as the shape parameter. These surfaces, a generalization of Bézier surfaces, have applications in mathematics, computer-aided geometric design, and computer graphics for the surface formation and modeling. We analyze the timelike and spacelike cases of q-Bernstein-Bézier surfaces using known boundary control points. The mean curvature and Gaussian curvature of these q-Bernstein-Bézier surfaces are computed by finding the respective fundamental coefficients. We also investigate the shape operator dependency for timelike and spacelike q-Bernstein-Bézier surfaces in Minkowski space- R13 , and provide biquadratic and bicubic q-Bernstein-Bézier surfaces as illustrative examples for different values of the shape controlling parameter q. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Almost periodic synchronization of quaternion-valued shunting inhibitory cellular neural networks with mixed delays via state-feedback control.
- Author
-
Li, Yongkun and Wang, Huimei
- Subjects
CELLULAR neural networks (Computer science) ,FEEDBACK control systems ,ABELIAN groups ,BANACH spaces ,FIXED point theory - Abstract
This paper studies the drive-response synchronization for quaternion-valued shunting inhibitory cellular neural networks (QVSICNNs) with mixed delays. First, QVSICNN is decomposed into an equivalent real-valued system in order to avoid the non-commutativity of the multiplicity. Then, the existence of almost periodic solutions is obtained based on the Banach fixed point theorem. An novel state-feedback controller is designed to ensure the global exponential almost periodic synchronization. At the end of the paper, an example is given to illustrate the effectiveness of the obtained results. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
4. A direct method to solve optimal knots of B-spline curves: An application for non-uniform B-spline curves fitting.
- Author
-
Dung, Van Than and Tjahjowidodo, Tegoeh
- Subjects
SPLINE theory ,COMPUTER graphics ,COMPUTER-aided design ,REVERSE engineering ,BENCHMARKING (Management) - Abstract
B-spline functions are widely used in many industrial applications such as computer graphic representations, computer aided design, computer aided manufacturing, computer numerical control, etc. Recently, there exist some demands, e.g. in reverse engineering (RE) area, to employ B-spline curves for non-trivial cases that include curves with discontinuous points, cusps or turning points from the sampled data. The most challenging task in these cases is in the identification of the number of knots and their respective locations in non-uniform space in the most efficient computational cost. This paper presents a new strategy for fitting any forms of curve by B-spline functions via local algorithm. A new two-step method for fast knot calculation is proposed. In the first step, the data is split using a bisecting method with predetermined allowable error to obtain coarse knots. Secondly, the knots are optimized, for both locations and continuity levels, by employing a non-linear least squares technique. The B-spline function is, therefore, obtained by solving the ordinary least squares problem. The performance of the proposed method is validated by using various numerical experimental data, with and without simulated noise, which were generated by a B-spline function and deterministic parametric functions. This paper also discusses the benchmarking of the proposed method to the existing methods in literature. The proposed method is shown to be able to reconstruct B-spline functions from sampled data within acceptable tolerance. It is also shown that, the proposed method can be applied for fitting any types of curves ranging from smooth ones to discontinuous ones. In addition, the method does not require excessive computational cost, which allows it to be used in automatic reverse engineering applications. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
5. Generic, network schema agnostic sparse tensor factorization for single-pass clustering of heterogeneous information networks.
- Author
-
Wu, Jibing, Meng, Qinggang, Deng, Su, Huang, Hongbin, Wu, Yahui, and Badii, Atta
- Subjects
SOCIAL media ,LEAST squares ,ALGORITHMS ,SOCIAL networks ,MATHEMATICAL optimization - Abstract
Heterogeneous information networks (e.g. bibliographic networks and social media networks) that consist of multiple interconnected objects are ubiquitous. Clustering analysis is an effective method to understand the semantic information and interpretable structure of the heterogeneous information networks, and it has attracted the attention of many researchers in recent years. However, most studies assume that heterogeneous information networks usually follow some simple schemas, such as bi-typed networks or star network schema, and they can only cluster one type of object in the network each time. In this paper, a novel clustering framework is proposed based on sparse tensor factorization for heterogeneous information networks, which can cluster multiple types of objects simultaneously in a single pass without any network schema information. The types of objects and the relations between them in the heterogeneous information networks are modeled as a sparse tensor. The clustering issue is modeled as an optimization problem, which is similar to the well-known Tucker decomposition. Then, an Alternating Least Squares (ALS) algorithm and a feasible initialization method are proposed to solve the optimization problem. Based on the tensor factorization, we simultaneously partition different types of objects into different clusters. The experimental results on both synthetic and real-world datasets have demonstrated that our proposed clustering framework, STFClus, can model heterogeneous information networks efficiently and can outperform state-of-the-art clustering algorithms as a generally applicable single-pass clustering method for heterogeneous network which is network schema agnostic. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
6. The morphing of geographical features by Fourier transformation.
- Author
-
Li, Jingzhong, Liu, Pengcheng, Yu, Wenhao, and Cheng, Xiaoqiang
- Subjects
FOURIER series ,MATHEMATICAL functions ,MORPHING (Computer animation) ,GEOINFORMATICS ,ENVIRONMENTAL sciences ,LINEAR statistical models - Abstract
This paper presents a morphing model of vector geographical data based on Fourier transformation. This model involves three main steps. They are conversion from vector data to Fourier series, generation of intermediate function by combination of the two Fourier series concerning a large scale and a small scale, and reverse conversion from combination function to vector data. By mirror processing, the model can also be used for morphing of linear features. Experimental results show that this method is sensitive to scale variations and it can be used for vector map features’ continuous scale transformation. The efficiency of this model is linearly related to the point number of shape boundary and the interceptive value n of Fourier expansion. The effect of morphing by Fourier transformation is plausible and the efficiency of the algorithm is acceptable. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
7. Performance improvement of haptic collision detection using subdivision surface and sphere clustering.
- Author
-
Choi, A. Ram and Sung, Mee Young
- Subjects
TOUCH ,COLLISION detection (Computer animation) ,SUBDIVISION surfaces (Geometry) ,SIMULATION methods & models ,BOUNDING - Abstract
Haptics applications such as surgery simulations require collision detections that are more precise than others. An efficient collision detection method based on the clustering of bounding spheres was proposed in our prior study. This paper analyzes and compares the applied effects of the five most common subdivision surface methods on some 3D models for haptic collision detection. The five methods are Butterfly, Catmull-Clark, Mid-point, Loop, and LS3 (Least Squares Subdivision Surface). After performing a number of experiments, we have concluded that LS3 method is the most appropriate for haptic simulations. The more we applied surface subdivision, the more the collision detection results became precise. However, it is observed that the performance becomes better until a certain threshold and degrades afterward. In order to reduce the performance degradation, we adopted our prior work, which was the fast and precise collision detection method based on adaptive clustering. As a result, we obtained a notable improvement of the speed of collision detection. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
8. LivePhantom: Retrieving Virtual World Light Data to Real Environments.
- Author
-
Kolivand, Hoshang, Billinghurst, Mark, and Sunar, Mohd Shahrizal
- Subjects
AUGMENTED reality ,KINECT (Motion sensor) ,IMAGE reconstruction ,VIRTUAL reality ,ALGORITHMS - Abstract
To achieve realistic Augmented Reality (AR), shadows play an important role in creating a 3D impression of a scene. Casting virtual shadows on real and virtual objects is one of the topics of research being conducted in this area. In this paper, we propose a new method for creating complex AR indoor scenes using real time depth detection to exert virtual shadows on virtual and real environments. A Kinect camera was used to produce a depth map for the physical scene mixing into a single real-time transparent tacit surface. Once this is created, the camera’s position can be tracked from the reconstructed 3D scene. Real objects are represented by virtual object phantoms in the AR scene enabling users holding a webcam and a standard Kinect camera to capture and reconstruct environments simultaneously. The tracking capability of the algorithm is shown and the findings are assessed drawing upon qualitative and quantitative methods making comparisons with previous AR phantom generation applications. The results demonstrate the robustness of the technique for realistic indoor rendering in AR systems. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
9. Fast and robust shape diameter function.
- Author
-
Chen, Shuangmin, Liu, Taijun, Shu, Zhenyu, Xin, Shiqing, He, Ying, and Tu, Changhe
- Subjects
SHAPE analysis (Computational geometry) ,DIAMETER ,GEODESIC equation ,COMPUTER graphics ,GAUSSIAN mixture models - Abstract
The shape diameter function (SDF) is a scalar function defined on a closed manifold surface, measuring the neighborhood diameter of the object at each point. Due to its pose oblivious property, SDF is widely used in shape analysis, segmentation and retrieval. However, computing SDF is computationally expensive since one has to place an inverted cone at each point and then average the penetration distances for a number of rays inside the cone. Furthermore, the shape diameters are highly sensitive to local geometric features as well as the normal vectors, hence diminishing their applications to real-world meshes which often contain rich geometric details and/or various types of defects, such as noise and gaps. In order to increase the robustness of SDF and promote it to a wide range of 3D models, we define SDF by offsetting the input object a little bit. This seemingly minor change brings three significant benefits: First, it allows us to compute SDF in a robust manner since the offset surface is able to give reliable normal vectors. Second, it runs many times faster since at each point we only need to compute the penetration distance along a single direction, rather than tens of directions. Third, our method does not require watertight surfaces as the input—it supports both point clouds and meshes with noise and gaps. Extensive experimental results show that the offset-surface based SDF is robust to noise and insensitive to geometric details, and it also runs about 10 times faster than the existing method. We also exhibit its usefulness using two typical applications including shape retrieval and shape segmentation, and observe a significant improvement over the existing SDF. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
10. A direct method to solve optimal knots of B-spline curves: An application for non-uniform B-spline curves fitting
- Author
-
Van Than Dung, Tegoeh Tjahjowidodo, Wu, Rongling, and School of Mechanical and Aerospace Engineering
- Subjects
Polynomial ,Computer science ,Statistics as Topic ,lcsh:Medicine ,02 engineering and technology ,Least squares ,Polynomials ,Computer Applications ,Mathematical and Statistical Techniques ,0202 electrical engineering, electronic engineering, information engineering ,Medicine and Health Sciences ,Parametric equation ,lcsh:Science ,Immune Response ,Multidisciplinary ,Direct method ,Applied Mathematics ,Simulation and Modeling ,Curve Fitting ,Multidisciplinary Sciences ,Ordinary least squares ,Physical Sciences ,Curve fitting ,Science & Technology - Other Topics ,Computer-Aided Design ,020201 artificial intelligence & image processing ,Algorithm ,Algorithms ,Research Article ,Optimization ,Computer and Information Sciences ,Immunology ,Clonal Selection ,Research and Analysis Methods ,Knot (unit) ,OPTIMIZATION APPROACH ,Computer Graphics ,Computer Simulation ,ALGORITHM ,Science & Technology ,B-spline ,lcsh:R ,Biology and Life Sciences ,020207 software engineering ,Computing Methods ,Algebra ,Family of curves ,lcsh:Q ,POINTS ,Nonlinear Least Squares Method ,Mathematical Functions ,Mathematics ,APPROXIMATION - Abstract
B-spline functions are widely used in many industrial applications such as computer graphic representations, computer aided design, computer aided manufacturing, computer numerical control, etc. Recently, there exist some demands, e.g. in reverse engineering (RE) area, to employ B-spline curves for non-trivial cases that include curves with discontinuous points, cusps or turning points from the sampled data. The most challenging task in these cases is in the identification of the number of knots and their respective locations in non-uniform space in the most efficient computational cost. This paper presents a new strategy for fitting any forms of curve by B-spline functions via local algorithm. A new two-step method for fast knot calculation is proposed. In the first step, the data is split using a bisecting method with predetermined allowable error to obtain coarse knots. Secondly, the knots are optimized, for both locations and continuity levels, by employing a non-linear least squares technique. The B-spline function is, therefore, obtained by solving the ordinary least squares problem. The performance of the proposed method is validated by using various numerical experimental data, with and without simulated noise, which were generated by a B-spline function and deterministic parametric functions. This paper also discusses the benchmarking of the proposed method to the existing methods in literature. The proposed method is shown to be able to reconstruct B-spline functions from sampled data within acceptable tolerance. It is also shown that, the proposed method can be applied for fitting any types of curves ranging from smooth ones to discontinuous ones. In addition, the method does not require excessive computational cost, which allows it to be used in automatic reverse engineering applications. ispartof: PLOS ONE vol:12 issue:3 ispartof: location:United States status: published
- Published
- 2017
11. Discrimination Power of Polynomial-Based Descriptors for Graphs by Using Functional Matrices
- Author
-
Matthias Dehmer, Frank Emmert-Streib, Yongtang Shi, Monica Stefu, and Shailesh Tripathi
- Subjects
Science ,Computer Graphics ,Medicine ,Mathematics ,Research Article - Abstract
In this paper, we study the discrimination power of graph measures that are based on graph-theoretical matrices. The paper generalizes the work of [M. Dehmer, M. Moosbrugger. Y. Shi, Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix, Applied Mathematics and Computation, 268(2015), 164-168]. We demonstrate that by using the new functional matrix approach, exhaustively generated graphs can be discriminated more uniquely than shown in the mentioned previous work.
- Published
- 2015
12. A quadratic trigonometric spline for curve modeling.
- Author
-
Samreen, Shamaila, Sarfraz, Muhammad, and Hussain, Malik Zawwar
- Subjects
SPLINES ,TRIGONOMETRIC functions ,GEOMETRIC analysis ,NUMERICAL analysis ,MATHEMATICAL models - Abstract
An imperative curve modeling technique has been established with a view to its applications in various disciplines of science, engineering and design. It is a new spline method using piecewise quadratic trigonometric functions. It possesses error bounds of order 3. The proposed curve model also owns the most favorable geometric properties. The proposed spline method accomplishes C
2 smoothness and produces a Quadratic Trigonometric Spline (QTS) with the view to its applications in curve design and control. It produces a C2 quadratic trigonometric alternative to the traditional cubic polynomial spline (CPS) because of having four control points in its piecewise description. The comparison analysis of QTS and CPS verifies the QTS as better alternate to CPS. Also, the time analysis proves QTS computationally efficient than CPS. [ABSTRACT FROM AUTHOR]- Published
- 2019
- Full Text
- View/download PDF
13. Hexahedral mesh generation via constrained quadrilateralization.
- Author
-
Shang, Feifei, Gan, Yangke, and Guo, Yufei
- Subjects
NUMERICAL grid generation (Numerical analysis) ,COMPUTER graphics ,POLYGONS ,FINITE element method ,MATHEMATICAL continuum - Abstract
Decomposing a volume into high-quality hexahedral cells is a challenging task in finite element simulations and computer graphics. Inspired by the use of a spatial twist continuum and frame field in previous hexahedral mesh generation methods, we present a method of hexahedral mesh generation via constrained quadrilateralization that combines a spatial twist continuum and frame fields. Given a volume represented by a tetrahedral mesh, surface quadrilateral mesh and frame field, we first extend the loop of the surface of a solid to a layer of hexahedral elements, then divide the solid into two smaller sub-solids by the layer, and finally handle them recursively until all of the sub-solids are empty. In our hexahedral mesh generation framework, we apply constrained quadrilateralization to extend the loop to a layer of hexahedral elements. The “divide-and-conquer” strategy used in this method is suitable for parallelization. This method can potentially lead to easier and more robust implementations that are more parallelizable and less dependent on heavy numerical libraries. The testing results show that the quality of the meshes generated by this method is similar to those produced by current state-of-the-art mesh generation methods. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
14. A Framework for Analyzing the Whole Body Surface Area from a Single View.
- Author
-
Piccirilli, Marco, Doretto, Gianfranco, and Adjeroh, Donald
- Subjects
DATA acquisition systems ,INFORMATION storage & retrieval systems ,BODY surface area ,MACHINE learning ,ARTIFICIAL intelligence - Abstract
We present a virtual reality (VR) framework for the analysis of whole human body surface area. Usual methods for determining the whole body surface area (WBSA) are based on well known formulae, characterized by large errors when the subject is obese, or belongs to certain subgroups. For these situations, we believe that a computer vision approach can overcome these problems and provide a better estimate of this important body indicator. Unfortunately, using machine learning techniques to design a computer vision system able to provide a new body indicator that goes beyond the use of only body weight and height, entails a long and expensive data acquisition process. A more viable solution is to use a dataset composed of virtual subjects. Generating a virtual dataset allowed us to build a population with different characteristics (obese, underweight, age, gender). However, synthetic data might differ from a real scenario, typical of the physician’s clinic. For this reason we develop a new virtual environment to facilitate the analysis of human subjects in 3D. This framework can simulate the acquisition process of a real camera, making it easy to analyze and to create training data for machine learning algorithms. With this virtual environment, we can easily simulate the real setup of a clinic, where a subject is standing in front of a camera, or may assume a different pose with respect to the camera. We use this newly designated environment to analyze the whole body surface area (WBSA). In particular, we show that we can obtain accurate WBSA estimations with just one view, virtually enabling the possibility to use inexpensive depth sensors (e.g., the Kinect) for large scale quantification of the WBSA from a single view 3D map. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
15. Interactive Tooth Separation from Dental Model Using Segmentation Field.
- Author
-
Li, Zhongyi and Wang, Hao
- Subjects
ORTHODONTICS ,DENTISTRY ,IMAGE segmentation ,COMPUTER-aided design ,LINEAR systems - Abstract
Tooth segmentation on dental model is an essential step of computer-aided-design systems for orthodontic virtual treatment planning. However, fast and accurate identifying cutting boundary to separate teeth from dental model still remains a challenge, due to various geometrical shapes of teeth, complex tooth arrangements, different dental model qualities, and varying degrees of crowding problems. Most segmentation approaches presented before are not able to achieve a balance between fine segmentation results and simple operating procedures with less time consumption. In this article, we present a novel, effective and efficient framework that achieves tooth segmentation based on a segmentation field, which is solved by a linear system defined by a discrete Laplace-Beltrami operator with Dirichlet boundary conditions. A set of contour lines are sampled from the smooth scalar field, and candidate cutting boundaries can be detected from concave regions with large variations of field data. The sensitivity to concave seams of the segmentation field facilitates effective tooth partition, as well as avoids obtaining appropriate curvature threshold value, which is unreliable in some case. Our tooth segmentation algorithm is robust to dental models with low quality, as well as is effective to dental models with different levels of crowding problems. The experiments, including segmentation tests of varying dental models with different complexity, experiments on dental meshes with different modeling resolutions and surface noises and comparison between our method and the morphologic skeleton segmentation method are conducted, thus demonstrating the effectiveness of our method. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
16. ABrox—A user-friendly Python module for approximate Bayesian computation with a focus on model comparison
- Author
-
Mertens, Ulf Kai, Voss, Andreas, and Radev, Stefan
- Subjects
Man-Computer Interface ,Computer and Information Sciences ,Decision Analysis ,Normal Distribution ,lcsh:Medicine ,Research and Analysis Methods ,Computer Architecture ,Machine Learning ,Machine Learning Algorithms ,User-Computer Interface ,Artificial Intelligence ,Computer Graphics ,lcsh:Science ,Stochastic Processes ,Software Tools ,Simulation and Modeling ,Applied Mathematics ,lcsh:R ,Decision Trees ,Software Engineering ,Bayes Theorem ,Models, Theoretical ,Probability Theory ,Probability Distribution ,Decision Tree Learning ,Physical Sciences ,Human Factors Engineering ,Engineering and Technology ,lcsh:Q ,Graphical User Interface ,Management Engineering ,Mathematics ,Algorithms ,Software ,Research Article ,User Interfaces - Abstract
We give an overview of the basic principles of approximate Bayesian computation (ABC), a class of stochastic methods that enable flexible and likelihood-free model comparison and parameter estimation. Our new open-source software called ABrox is used to illustrate ABC for model comparison on two prominent statistical tests, the two-sample t-test and the Levene-Test. We further highlight the flexibility of ABC compared to classical Bayesian hypothesis testing by computing an approximate Bayes factor for two multinomial processing tree models. Last but not least, throughout the paper, we introduce ABrox using the accompanied graphical user interface.
- Published
- 2018
17. Combinatorial algorithm for counting small induced graphs and orbits
- Author
-
Janez Demšar and Tomaž Hočevar
- Subjects
0301 basic medicine ,Vertex (graph theory) ,FOS: Computer and information sciences ,Proteomics ,Discrete Mathematics (cs.DM) ,Computer science ,Gene Identification and Analysis ,lcsh:Medicine ,Social Sciences ,Genetic Networks ,01 natural sciences ,Infographics ,Biochemistry ,Database and Informatics Methods ,Sociology ,Protein Interaction Mapping ,Enumeration ,Data Structures and Algorithms (cs.DS) ,Gene Regulatory Networks ,lcsh:Science ,Multidisciplinary ,Quantitative Biology::Molecular Networks ,Applied Mathematics ,Simulation and Modeling ,Graph ,Social Networks ,010201 computation theory & mathematics ,Physical Sciences ,Protein Interaction Networks ,Graphs ,Algorithms ,Network Analysis ,Research Article ,Computer and Information Sciences ,Bioinformatics ,0102 computer and information sciences ,Combinatorial algorithms ,System of linear equations ,Research and Analysis Methods ,Models, Biological ,03 medical and health sciences ,Computer Science - Data Structures and Algorithms ,Genetics ,Computer Graphics ,Computer Simulation ,Protein Interactions ,Discrete mathematics ,Electronic Data Processing ,Data Visualization ,lcsh:R ,Biology and Life Sciences ,Proteins ,Computational Biology ,Models, Theoretical ,Vertex (geometry) ,030104 developmental biology ,Protein-Protein Interactions ,lcsh:Q ,Mathematics ,Computer Science - Discrete Mathematics - Abstract
Graphlet analysis is an approach to network analysis that is particularly popular in bioinformatics. We show how to set up a system of linear equations that relate the orbit counts and can be used in an algorithm that is significantly faster than the existing approaches based on direct enumeration of graphlets. The approach presented in this paper presents a generalization of the currently fastest method for counting 5-node graphlets in bioinformatics. The algorithm requires existence of a vertex with certain properties; we show that such vertex exists for graphlets of arbitrary size, except for complete graphs and a cycle with four nodes, which are treated separately. Empirical analysis of running time agrees with the theoretical results.
- Published
- 2017
18. Approximate Counting of Graphical Realizations
- Author
-
Péter L. Erdős, Sándor Z. Kiss, István Miklós, and Lajos Soukup
- Subjects
Discrete mathematics ,Polynomial ,Multidisciplinary ,Conjecture ,Markov chain ,lcsh:R ,lcsh:Medicine ,Directed graph ,Models, Theoretical ,Small set ,Markov Chains ,Sampling Studies ,Computer Communication Networks ,Mixing (mathematics) ,Bipartite graph ,Computer Graphics ,lcsh:Q ,Computer Simulation ,lcsh:Science ,Heuristics ,Algorithms ,Mathematics ,Research Article - Abstract
In 1999 Kannan, Tetali and Vempala proposed a MCMC method to uniformly sample all possible realizations of a given graphical degree sequence and conjectured its rapidly mixing nature. Recently their conjecture was proved affirmative for regular graphs (by Cooper, Dyer and Greenhill, 2007), for regular directed graphs (by Greenhill, 2011) and for half-regular bipartite graphs (by Miklos, Erdős and Soukup, 2013). Several heuristics on counting the number of possible realizations exist (via sampling processes), and while they work well in practice, so far no approximation guarantees exist for such an approach. This paper is the first to develop a method for counting realizations with provable approximation guarantee. In fact, we solve a slightly more general problem; besides the graphical degree sequence a small set of forbidden edges is also given. We show that for the general problem (which contains the Greenhill problem and the Miklos, Erdős and Soukup problem as special cases) the derived MCMC process is rapidly mixing. Further, we show that this new problem is self-reducible therefore it provides a fully polynomial randomized approximation scheme (a.k.a. FPRAS) for counting of all realizations.
- Published
- 2015
19. On the Treewidths of Graphs of Bounded Degree
- Author
-
Menghong Yu and Yinglei Song
- Subjects
Models, Molecular ,Multidisciplinary ,Clique-sum ,Degree (graph theory) ,lcsh:R ,lcsh:Medicine ,Computer Science::Computational Complexity ,Tree-depth ,1-planar graph ,Biophysical Phenomena ,Combinatorics ,Treewidth ,Pathwidth ,Computer Science::Discrete Mathematics ,Chordal graph ,Partial k-tree ,Computer Graphics ,Humans ,Quantum Theory ,lcsh:Q ,Computer Science::Data Structures and Algorithms ,lcsh:Science ,Algorithms ,Mathematics ,Research Article - Abstract
In this paper, we develop a new technique to study the treewidth of graphs with bounded degree. We show that the treewidth of a graph G = (V, E) with maximum vertex degree d is at most [Formula: see text] for sufficiently large d, where C is a constant.
- Published
- 2015
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.