Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Graphs (5)
- Algorithms (3)
- Recognition algorithm (3)
- Cographs (2)
- Optimal algorithms (2)
-
- P4-sparse graphs (2)
- Parallel algorithms (2)
- Scheduling (2)
- Tree representation (2)
- Vertices (2)
- Applications (1)
- Applied computing (1)
- Artificial intelligence (1)
- Axially symmetric body (1)
- Binary trees (1)
- Boundary condition (1)
- Cluster analysis (1)
- Comparability graphs (1)
- Computer forensics (1)
- Computing methodologies (1)
- Convergence (1)
- Decoding (1)
- Efficient algorithms (1)
- Electromagnetic scattering (1)
- Encoding (1)
- Greedy algorithms (1)
- Group-based collaboration (1)
- Hamitonicity (1)
- Hierarchical graph decompositions (1)
- Interval graphs (1)
Articles 1 - 20 of 20
Full-Text Articles in Physical Sciences and Mathematics
Camouflaged Poisoning Attack On Graph Neural Networks, Chao Jiang, Yi He, Richard Chapman, Hongyi Wu
Camouflaged Poisoning Attack On Graph Neural Networks, Chao Jiang, Yi He, Richard Chapman, Hongyi Wu
Computer Science Faculty Publications
Graph neural networks (GNNs) have enabled the automation of many web applications that entail node classification on graphs, such as scam detection in social media and event prediction in service networks. Nevertheless, recent studies revealed that the GNNs are vulnerable to adversarial attacks, where feeding GNNs with poisoned data at training time can lead them to yield catastrophically devastative test accuracy. This finding heats up the frontier of attacks and defenses against GNNs. However, the prior studies mainly posit that the adversaries can enjoy free access to manipulate the original graph, while obtaining such access could be too costly in …
Momcmc: An Efficient Monte Carlo Method For Multi-Objective Sampling Over Real Parameter Space, Yaohang Li
Momcmc: An Efficient Monte Carlo Method For Multi-Objective Sampling Over Real Parameter Space, Yaohang Li
Computer Science Faculty Publications
In this paper, we present a new population-based Monte Carlo method, so-called MOMCMC (Multi-Objective Markov Chain Monte Carlo). for sampling in the presence of multiple objective functions in real parameter space. The MOMCMC method is designed to address the "multi-objective sampling" problem, which is not only of interest in exploring diversified solutions at the Pareto optimal front in the function space of multiple objective functions, but also those near the front. MOMCMC integrates Differential Evolution (DE) style crossover into Markov Chain Monte Carlo (MCMC) to adaptively propose new solutions from the current population. The significance of dominance is taken into …
Upper Bounds To The Clique Width Of Graphs, Bruno Courcelle, Stephan Olariu
Upper Bounds To The Clique Width Of Graphs, Bruno Courcelle, Stephan Olariu
Computer Science Faculty Publications
Hierarchical decompositions of graphs are interesting for algorithmic purposes. Many NP complete problems have linear complexity on graphs with tree-decompositions of bounded width. We investigate alternate hierarchical decompositions that apply to wider classes of graphs and still enjoy good algorithmic properties. These decompositions are motivated and inspired by the study of vertex-replacement context-free graph grammars. The complexity measure of graphs associated with these decompositions is called clique width. In this paper we bound the clique width of a graph in terms of its tree width on the one hand, and of the clique width of its edge complement on …
On The P-Connectedness Of Graphs – A Survey, Luitpold Babel, Stephan Olariu
On The P-Connectedness Of Graphs – A Survey, Luitpold Babel, Stephan Olariu
Computer Science Faculty Publications
A graph is said to be p-connected if for every partition of its vertices into two non-empty, disjoint, sets some chordless path with three edges contains vertices from both sets in the partition. As it turns out, p-connectedness generalizes the usual connectedness of graphs and leads, in a natural way, to a unique tree representation for arbitrary graphs.
This paper reviews old and new results, both structural and algorithmic, about p-connectedness along with applications to various graph decompositions.
A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu
A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu
Computer Science Faculty Publications
A number of problems in mobile computing, group-based collaboration, automated theorem proving, networking, scheduling, and cluster analysis suggested the study of graphs featuring certain “local density” characteristics. Typically, the notion of local density is equated with the absence of chordless paths of length three or more. Recently, a new metric for local density has been proposed, allowing a number of such induced paths to occur. More precisely, a graphG is called P4-sparse if no set of five vertices inG induces more than one chordless path of length three. P4-sparse graphs generalize the well-known class of cographs corresponding to …
On The Structure Of Graphs With Few P4s, Luitpold Babel, Stephan Olariu
On The Structure Of Graphs With Few P4s, Luitpold Babel, Stephan Olariu
Computer Science Faculty Publications
We present new classes of graphs for which the isomorphism problem can be solved in polynomial time. These graphs are characterized by containing — in some local sense — only a small number of induced paths of length three. As it turns out, every such graph has a unique tree representation: the internal nodes correspond to three types of graph operations, while the leaves are basic graphs with a simple structure. The paper extends and generalizes known results about cographs, P4-reducible graphs, and P4-sparse graphs.
Time-Optimal Tree Computations On Sparse Meshes, D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J. L. Schwing
Time-Optimal Tree Computations On Sparse Meshes, D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J. L. Schwing
Computer Science Faculty Publications
The main goal of this work is to fathom the suitability of the mesh with multiple broadcasting architecture (MMB) for some tree-related computations. We view our contribution at two levels: on the one hand, we exhibit time lower bounds for a number of tree-related problems on the MMB. On the other hand, we show that these lower bounds are tight by exhibiting time-optimal tree algorithms on the MMB. Specifically, we show that the task of encoding and/or decoding n-node binary and ordered trees cannot be solved faster than Ω(log n) time even if the MMB has an infinite …
Linear Time Optimization Algorithms For P4-Sparse Graphs, Beverly Jamison, Stephan Olariu
Linear Time Optimization Algorithms For P4-Sparse Graphs, Beverly Jamison, Stephan Olariu
Computer Science Faculty Publications
Quite often, real-life applications suggest the study of graphs that feature some local density properties. In particular, graphs that are unlikely to have more than a few chordless paths of length three appear in a number of contexts. A graph G is P4-sparse if no set of five vertices in G induces more than one chordless path of length three. P4-sparse graphs generalize both the class of cographs and the class of P4-reducible graphs. It has been shown that P4-sparse graphs can be recognized in time linear in the size of the …
An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu
An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu
Computer Science Faculty Publications
The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. In this paper, we present an optimal algorithm for determining a minimum path cover for a cograph G. In case G has a Hamiltonian path (cycle) our algorithm exhibits the path (cycle) as well.
Optimal Greedy Algorithms For Indifference Graphs, Peter J. Looges, Stephan Olariu
Optimal Greedy Algorithms For Indifference Graphs, Peter J. Looges, Stephan Olariu
Computer Science Faculty Publications
A fundamental problem in social sciences and management is understanding and predicting decisions made by individuals, various groups, or the society as a whole. In this context, one important concept is the notion of indifference. We characterize the class of indifference graphs, that is, graphs which arise in the process of quantifying indifference relations. In particular, we show that these graphs are characterized by the existence of a special ordering of their vertices. As it turns out, this ordering leads naturally to optimal greedy algorithms for a number of computational problems, including coloring, finding a shortest path between two vertices, …
Quasi-Brittle Graphs, A New Class Of Perfectly Orderable Graphs, Stephan Olariu
Quasi-Brittle Graphs, A New Class Of Perfectly Orderable Graphs, Stephan Olariu
Computer Science Faculty Publications
A graph G is quasi-brittle if every induced subgraph H of G contains a vertex which is incident to no edge extending symmetrically to a chordless path with three edges in either Hor its complement H¯. The quasi-brittle graphs turn out to be a natural generalization of the well-known class of brittle graphs. We propose to show that the quasi-brittle graphs are perfectly orderable in the sense of Chvátal: there exists a linear order < on their set of vertices such that no induced path with vertices a, b, c, d and edges ab, bc, cd has a < b and d < c.
The Morphology Of Convex Polygons, Stephan Olariu
The Morphology Of Convex Polygons, Stephan Olariu
Computer Science Faculty Publications
A simple polygon P is said to be unimodal if for every vertex of P, the Euclidian distance function to the other vertices of P is unimodal. The study of unimodal polygons has emerged as a fruitful area of computational and discrete geometry. We study unimodality properties of a number of special convex polygons from the morphological point of view. In particular, we establish a hierarchy among three classes of convex polygons in terms of their unimodality properties.
A Tree Representation For P4-Sparse Graphs, B. Jamison, Stephan Olariu
A Tree Representation For P4-Sparse Graphs, B. Jamison, Stephan Olariu
Computer Science Faculty Publications
A graph G is P4-sparse if no set of five vertices in G induces more than one chordless path of length three. P4-sparse graphs generalize both the class of cographs and the class of P4-reducible graphs. We give several characterizations for P4-sparse graphs and show that they can be constructed from single-vertex graphs by a finite sequence of operations. Our characterization implies that the P4-sparse graphs admit a tree representation unique up to isomorphism. Furthermore, this tree representation can be obtained in polynomial time.
On Sources In Comparability Graphs, With Applications, Stephan Olariu
On Sources In Comparability Graphs, With Applications, Stephan Olariu
Computer Science Faculty Publications
We characterize sources in comparability graphs and show that our result provides a unifying look at two recent results about interval graphs.
A Charming Class Of Perfectly Orderable Graphs, Chinh T. Hoang, Frederic Maffray, Stephan Olariu, Myriam Preissmann
A Charming Class Of Perfectly Orderable Graphs, Chinh T. Hoang, Frederic Maffray, Stephan Olariu, Myriam Preissmann
Computer Science Faculty Publications
We investigate the following conjecture of Vašek Chvátal: any weakly triangulated graph containing no induced path on five vertices is perfectly orderable. In the process we define a new polynomially recognizable class of perfectly orderable graphs called charming. We show that every weakly triangulated graph not containing as an induced subgraph a path on five vertices or the complement of a path on six vertices is charming.
Some Aspects Of The Semi-Perfect Elimination, Stephan Olariu
Some Aspects Of The Semi-Perfect Elimination, Stephan Olariu
Computer Science Faculty Publications
Several efficient algorithms have been proposed to construct a perfect elimination ordering of the vertices of a chordal graph. We study the behaviour of two of these algorithms in relation to a new concept, namely the semi-perfect elimination ordering, which provides a natural generalization of chordal graphs.
On A Unique Tree Representation For P4-Extendible Graphs, B. Jamison, S. Olariu
On A Unique Tree Representation For P4-Extendible Graphs, B. Jamison, S. Olariu
Computer Science Faculty Publications
Several practical applications in computer science and computational linguistics suggest the study of graphs that are unlikely to have more than a few induced paths of length three. These applications have motivated the notion of a cograph, defined by the very strong restriction that no vertex may belong to an induced path of length three. The class of P4-extendible graphs that we introduce in this paper relaxes this restriction, and in fact properly contains the class of cographs, while still featuring the remarkable property of admitting a unique tree representation. Just as in the case of cographs, the …
Wings And Perfect Graphs, Stephan Olariu
Wings And Perfect Graphs, Stephan Olariu
Computer Science Faculty Publications
An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in G. A graph G is saturated if G is isomorphic to W(G). A star-cutset in a graph G is a non-empty set of …
Weak Bipolarizable Graphs, Stephan Olariu
Weak Bipolarizable Graphs, Stephan Olariu
Computer Science Faculty Publications
We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.
An Algorithm For The Electromagnetic Scattering Due To An Axially Symmetric Body With An Impedance Boundary Condition, F. Stenger, M. Hagmann, J. Scheing
An Algorithm For The Electromagnetic Scattering Due To An Axially Symmetric Body With An Impedance Boundary Condition, F. Stenger, M. Hagmann, J. Scheing
Computer Science Faculty Publications
Let B be a body in R3, and let S denote the boundary of B. The surface S is described by S = {(x, y, z): (x2 + Y2)½= ƒ(z), -1≤ z ≤ I}, where ƒ analytic function that is real and positive on (-1, 1) and ƒ(±1) = 0. An algorithm is described for computing the scattered field due to a plane wave incident field, under Leontovich boundary conditions. The Galerkin method of solution used here leads to a block diagonal matrix involving 2M …