A homogeneous set is a non-trivial module of a graph, i.e. a non-empty, non-unitary, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs G(1...
详细信息
A homogeneous set is a non-trivial module of a graph, i.e. a non-empty, non-unitary, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs G(1)(V, E-1), G(2)(V, E-2), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a sandwich graph G(S) (V, E-S), E-1 subset of E-S subset of E-2, which has a homogeneous set. In 2001 Tang et al. [ 15] published an all-fast O(n(2)Delta(2)) algorithm which was recently proven wrong [ 5], so that the HSSP's known upper bound would have been reset thereafter at the former O(n(4)) determined by Cerioli et al. [ 1] in 1998. We present, notwithstanding, new deterministic algorithms which have it established at O(n(3) log(m/n)). We give as well two even faster O(n(3)) randomized algorithms, whose simplicity might lend them didactic usefulness. We believe that, besides providing efficient easy-to-implement procedures to solve it, the study of these new approaches allows a fairly thorough understanding of the problem.
Based on the original idea of Sowa on conceptual graph and a recent formalism by Corbett on ontology, this paper presents a rigorous mathematization of basic concepts encountered in the Conceptual Structure Theory, in...
详细信息
Based on the original idea of Sowa on conceptual graph and a recent formalism by Corbett on ontology, this paper presents a rigorous mathematization of basic concepts encountered in the Conceptual Structure Theory, including canon, ontology, conceptual graph, projection, and canonical formation operations, with the aim of deriving their mathematical properties and applying them to future research and development on knowledge representation. Our proposed formalism enhances the Conceptual Structure Theory and enables it to compare favorably with other alternative methods such as the Formal Concept Analysis theory.
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers. In this paper we ...
详细信息
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers. In this paper we study the 2-Layer Planarization problem: Can k edges be deleted from a given graph G so that the remaining graph is biplanar? This problem is NP-complete, and remains so if the permutation of the vertices in one layer is fixed (the 1-Layer Planarization problem). We prove that these problems are fixed-parameter tractable by giving linear-time algorithms for their solution (for fixed k). In particular, we solve the 2-Layer Planarization problem in O(k . 6(k) + |G|) time and the 1-Layer Planarization problem in O(3(k) . |G|) time. We also show that there are polynomial-time constant-approximation algorithms for both problems.
A path cover of a graph G = (V, E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simp...
详细信息
A path cover of a graph G = (V, E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs. (c) 2005 Elsevier B.V. All rights reserved.
The k-LEAF POWERrecognition problem is a particular case of graph power problems: For a given graph it asks whether there exists an unrooted tree-the k-leaf root-with leaves one-to-one labeled by the graph vertices an...
详细信息
The k-LEAF POWERrecognition problem is a particular case of graph power problems: For a given graph it asks whether there exists an unrooted tree-the k-leaf root-with leaves one-to-one labeled by the graph vertices and where the leaves have distance at most k iff their corresponding vertices in the graph are connected by an edge. Here we study "error correction" versions of k-Leaf Power recognition-that is, adding or deleting at most l edges to generate a graph that has a k-leaf root. We provide several NP-completeness results in this context, and we show that the NP-complete Closest 3-LEAF POWER problem (the error correction version of 3-LEAF POWER) is fixed-parameter tractable with respect to the number of edge modifications or vertex deletions in the given graph. Thus, we provide the seemingly first nontrivial positive algorithmic results in the field of error compensation for leaf power problems with k > 2. To this end, as a result of independent interest, we develop a forbidden subgraph characterization of graphs with 3-leaf roots.
A homogeneous set is a non-trivial module of a graph, i.e., a non-empty, non-unitary, proper vertex subset such that all its elements present the same outer neighborhood. Given two graphs G(1) (V, E-1) and G(2)(V, E-2...
详细信息
A homogeneous set is a non-trivial module of a graph, i.e., a non-empty, non-unitary, proper vertex subset such that all its elements present the same outer neighborhood. Given two graphs G(1) (V, E-1) and G(2)(V, E-2), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a graph G(S)(V, E-S), E-1 subset of E-S subset of E-2, which has a homogeneous set. This paper presents an algorithm that uses the concept of bias graph [S. Tang, F. Yeh, Y Wang, An efficient algorithm for solving the homogeneous set sandwich problem, Inform. Process. Lett. 77 (2001) 17-22] to solve the problem in O(n min{vertical bar E-1 vertical bar, vertical bar(E) over bar (2)vertical bar} log n) time, thus outperforming the other known HSSP deterministic algorithms for inputs where max{vertical bar E-1 vertical bar, vertical bar(E) over bar (2)vertical bar} = Omega (n log n). (c) 2006 Elsevier B.V. All fights reserved.
This paper presents a methodology and a tool for automatic synthesis of highly efficient intrusion detection systems using a high-level, graph-based partitioning methodology and tree-based lookahead architectures. Int...
详细信息
This paper presents a methodology and a tool for automatic synthesis of highly efficient intrusion detection systems using a high-level, graph-based partitioning methodology and tree-based lookahead architectures. Intrusion detection for network security is a compute-intensive application demanding high system performance. The tools implement and automate a customizable flow for the creation of efficient Field Programmable Gate Array (FPGA) architectures using system-level optimizations. Our methodology allows for customized performance through more efficient communication and extensive reuse of hardware components for dramatic increases in area-time performance.
We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced "anchor technique" is based on a tree-like se...
详细信息
We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced "anchor technique" is based on a tree-like set covering problem. We substantiate our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%. (c) 2006 Elsevier B.V. All rights reserved.
We present a cubic-time algorithm for the following problem: Given a simple graph, decide whether it is realized by adjacencies of countries in a map without holes, in which at most four countries meet at any point.
We present a cubic-time algorithm for the following problem: Given a simple graph, decide whether it is realized by adjacencies of countries in a map without holes, in which at most four countries meet at any point.
The identification of design patterns as part of the reengineering process can convey important information to the designer. However, existing pattern detection methodologies generally have problems in dealing with on...
详细信息
The identification of design patterns as part of the reengineering process can convey important information to the designer. However, existing pattern detection methodologies generally have problems in dealing with one or more of the following issues: Identification of modified pattern versions, search space explosion for large systems and extensibility to novel patterns. In this paper, a design pattern detection methodology is proposed that is based on similarity scoring between graph vertices. Due to the nature of the underlying graph algorithm, this approach has the ability to also recognize patterns that are modified from their standard representation. Moreover, the approach exploits the fact that patterns reside in one or more inheritance hierarchies, reducing the size of the graphs to which the algorithm is applied. Finally, the algorithm does not rely on any pattern-specific heuristic, facilitating the extension to novel design structures. Evaluation on three open-source projects demonstrated the accuracy and the efficiency of the proposed method.
暂无评论