The problems of recognizing series-parallel graphs, outerplanar graphs, and generalized series-parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the a...
详细信息
The problems of recognizing series-parallel graphs, outerplanar graphs, and generalized series-parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is 'yes', and is negative if the answer is 'no'. In this paper, an O(|E| + |V |)-time certifying algorithm that simultaneously determines if a graph G = (V, E) is series- parallel, outerplanar, or generalized series-parallel is presented. The positive certificates are a construction sequence for constructing G if G is series-parallel, a generalized construction sequence for constructing G if G is generalized series-parallel but not series-parallel, and the edge set of the exterior boundary of an outerplanar embedding of G if G is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of G. All these certificates are generated by making only one pass over G after a preprocessing step decomposing G into its biconnected components.(c) 2022 Elsevier B.V. All rights reserved.
In a companion paper [P.R.J. Asveld, Fuzzy context-free languages-Part 1: Generalized fuzzy context-free grammars, Theoret. Comput. Sci. (2005)] we used fuzzy context-free grammars in order to model grammatical errors...
详细信息
In a companion paper [P.R.J. Asveld, Fuzzy context-free languages-Part 1: Generalized fuzzy context-free grammars, Theoret. Comput. Sci. (2005)] we used fuzzy context-free grammars in order to model grammatical errors resulting in erroneous inputs for robust recognizing and parsing algorithms for fuzzy context-free languages. In particular, this approach enables us to distinguish between small errors ("tiny mistakes") and big errors ("capital blunders"). In this paper, we present some algorithms to recognize fuzzy context-free languages: particularly, a modification of Cocke-Younger-Kasami's algorithm and some recursive descent algorithms. Then we extend these recognition algorithms to corresponding parsing algorithms for fuzzy context-free languages. These parsing algorithms happen to be robust in some very elementary sense. (c) 2005 Elsevier B.V. All rights reserved.
Exploiting geothermal resources such as hot dry rocks (HDRs) requires directional drilling technology. Measurement- while- drilling (MWD) technology plays a crucial role in directional measurement. However, its high t...
详细信息
Exploiting geothermal resources such as hot dry rocks (HDRs) requires directional drilling technology. Measurement- while- drilling (MWD) technology plays a crucial role in directional measurement. However, its high temperature and environment limit downhole measurement instruments in application. For this research, we designed an MWD system with a mechanical gravity tool face, and the fully mechanical structure was used to overcome the high- temperature constraints. The bias stabilization platform, gravity tool face coding method, and mud pulse generation structure were designed. The eccentric stable model and pulse generation structure model were established through numerical analysis, and a gravity tool face angle coding and identification method was also established. The experimental prototype testing system was built on theoretical analysis and hydrodynamics. The feasibility of the tool functions and the recognition algorithm were verified experimentally, with a maximum measurement error of 6 degrees and an average measurement error of 2.6 degrees. The average measurement error of the system in the well test is 6 degrees, which verifies the reliability of the system.
The k-path graph P-k(H) Of a graph H has all length-k paths of H as vertices;two such vertices are adjacent in the new graph if their union forms a path or cycle of length k + 1 in H, and if the common edges of both p...
详细信息
The k-path graph P-k(H) Of a graph H has all length-k paths of H as vertices;two such vertices are adjacent in the new graph if their union forms a path or cycle of length k + 1 in H, and if the common edges of both paths form a path of length k - 1. In this paper we give a (nonpolynomial) recognition algorithm for k-path graphs, for every integer k greater than or equal to 2. The algorithm runs in polynomial time if we are only interested in k-path graphs of graphs of high enough minimum degree. We also present an O(\V\(4))-time algorithm that decides whether for any input graph G = (V,E) there exist some integer k greater than or equal to 1 and some graph H of minimum degree at least k + 1 with G = P-k(H). If it is, we show that Ic and H are unique, extending previous uniqueness results by Xueliang Li. (C) 2000 Elsevier Science B.V. All rights reserved.
An odd hole in a graph is an induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an o...
详细信息
An odd hole in a graph is an induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an odd hole. We subsequently showed that, for every t, there is a polynomial-time algorithm to test whether a graph contains an odd hole of length at least t. In this article, we give an algorithm that finds a shortest odd hole, if one exists.
作者：
Takaoka, AsahiKanagawa Univ
Dept Informat Syst Creat Kanagawa Ku Rokkakubashi 3-27-1 Yokohama Kanagawa 2218686 Japan
A simple-triangle graph (also known as a PI graph) is the intersection graph of a family of triangles defined by a point on a horizontal line and an interval on another horizontal line. The recognition problem for sim...
详细信息
A simple-triangle graph (also known as a PI graph) is the intersection graph of a family of triangles defined by a point on a horizontal line and an interval on another horizontal line. The recognition problem for simple-triangle graphs was a longstanding open problem, and recently a polynomial-time algorithm has been given (Mertzios, 2015). Along with the approach of this paper, we show a simpler recognition algorithm for simple-triangle graphs. To do this, we introduce the following problem: given a bipartite graph G and a set F of edges of G, find a 2-chain subgraph cover of G such that one of two chain subgraphs has no edges in F. We show an O(n(2) . min{m, (m) over cap})-time algorithm for this problem, where n and m are the number of vertices and edges of G, respectively, and (m) over cap is the number of non-edges between two independent sets of G. Using this result, we show that the recognition problem for simple-triangle graphs can be solved in O(n(2) . min{m, (m) over bar}) time, where (m) over bar is the number of non-edges of the given graph. (C) 2019 Elsevier B.V. All rights reserved.
We use breadth-first search and contractions of subgraphs to give a new and faster algorithm to recognize i-triangulated graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
We use breadth-first search and contractions of subgraphs to give a new and faster algorithm to recognize i-triangulated graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
Raman spectroscopy has been increasingly researched this year. Due to the high accuracy, fast speed, and nondestructive detection features of Raman spectroscopy, there are more and more application scenarios. In this ...
详细信息
Raman spectroscopy has been increasingly researched this year. Due to the high accuracy, fast speed, and nondestructive detection features of Raman spectroscopy, there are more and more application scenarios. In this paper, a smart phone Raman system is studied. By the optical path design and slit coupling technology, the sensitivity of the device is improved while the size of the spectrometer itself is reduced. In order to improve the detection speed and accuracy, a cloud network architecture is proposed. The spectrometer is integrated into the backside of a smart phone and the wireless communication function of the smart phone can be used to realize the connection with the cloud server. The device terminal is only responsible for collecting and uploading data to the cloud. Spectra are identified by the algorithm server. The result and the attributes files are then transmitted to the smart Raman terminal. The algorithm, database, and terminal equipment are separated from each other to facilitate the timely update of algorithms and databases.
We introduce new versions of chordal and split digraphs, and explore their similarity with the corresponding undirected notions. (C) 2016 Elsevier B.V. All rights reserved.
We introduce new versions of chordal and split digraphs, and explore their similarity with the corresponding undirected notions. (C) 2016 Elsevier B.V. All rights reserved.
暂无评论