Search results for "MathematicsofComputing_DISCRETEMATHEMATICS"
showing 10 items of 123 documents
A segmentation algorithm for noisy images
2005
International audience; This paper presents a segmentation algorithm for gray-level images and addresses issues related to its performance on noisy images. It formulates an image segmentation problem as a partition of a weighted image neighborhood hypergraph. To overcome the computational difficulty of directly solving this problem, a multilevel hypergraph partitioning has been used. To evaluate the algorithm, we have studied how noise affects the performance of the algorithm. The alpha-stable noise is considered and its effects on the algorithm are studied. Key words : graph, hypergraph, neighborhood hypergraph, multilevel hypergraph partitioning, image segmentation and noise removal.
Combined column-and-row-generation for the optimal communication spanning tree problem
2018
Abstract This paper considers the exact solution of the optimal communication spanning tree problem (OCSTP), which can be described as follows: Given an undirected graph with transportation costs on every edge and communication requirements for all pairs of vertices, the OCSTP seeks for a spanning tree that minimizes the sum of the communication costs between all pairs of vertices, where the communication cost of a pair of vertices is defined as their communication requirement multiplied by the transportation cost of the unique tree path that connects the two vertices. Two types of compact formulations for OCSTP were presented in the literature. The first one is a four-index model based on …
Variable neighborhood descent for the incremental graph drawing
2017
Abstract Graphs are used to represent reality in several areas of knowledge. Drawings of graphs have many applications, from project scheduling to software diagrams. The main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion for a good representation of a graph. In this paper we target the edge crossing reduction in the context of incremental graph drawing, in which we want to preserve the layout of a graph over successive drawings. We propose a hybrid method based on the GRASP (Greedy Randomized Adaptive Search Procedure) and VND (Variable Neighborhood Descent) methodologies and compare it with previous methods via simulation.
Graph Rewriting Based Search for Molecular Structures: Definitions, Algorithms, Hardness
2018
We define a graph rewriting system that is easily understandable by humans, but rich enough to allow very general queries to molecule databases. It is based on the substitution of a single node in a node- and edge-labeled graph by an arbitrary graph, explicitly assigning new endpoints to the edges incident to the replaced node. For these graph rewriting systems, we are interested in the subgraph-matching problem. We show that the problem is NP-complete, even on graphs that are stars. As a positive result, we give an algorithm which is polynomial if both rules and query graph have bounded degree and bounded cut size. We demonstrate that molecular graphs of practically relevant molecules in d…
Measurement of the Lund jet plane using charged particles in 13 TeV proton-proton collisions with the ATLAS detector
2020
The prevalence of hadronic jets at the LHC requires that a deep understanding of jet formation and structure is achieved in order to reach the highest levels of experimental and theoretical precision. There have been many measurements of jet substructure at the LHC and previous colliders, but the targeted observables mix physical effects from various origins. Based on a recent proposal to factorize physical effects, this Letter presents a double-differential cross-section measurement of the Lund jet plane using 139 fb−1 of √s=13 TeV proton-proton collision data collected with the ATLAS detector using jets with transverse momentum above 675 GeV. The measurement uses charged particles to ac…
Dynamic 2- and 3-connectivity on planar graphs
1992
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total of O(n log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n log2n) time. This gives O(log2n) amortized time per deletion. The space required by all our data structures is O(n).
Extended Natural Numbers and Counters
2020
Summary This article introduces extended natural numbers, i.e. the set ℕ ∪ {+∞}, in Mizar [4], [3] and formalizes a way to list a cardinal numbers of cardinals. Both concepts have applications in graph theory.
The Windy clustered prize-collecting arc-routing problem
2011
This paper introduces the windy clustered prize-collecting arc-routing problem. It is an arc-routing problem where each demand edge is associated with a profit that is collected once if the edge is serviced, independent of the number of times the edge is traversed. It is further required that if a demand edge is serviced, then all the demand edges of its component are also serviced. A mathematical programming formulation is given and some polyhedral results including several facet-defining and valid inequalities are presented. The separation problem for the different families of inequalities is studied. Numerical results from computational experiments are analyzed. © 2011 INFORMS.
Optimal Guard Placement Problem Under L-Visibility
2006
Two points a and b in the presence of polygonal obstacles are L-visible if the length of the shortest path avoiding obstacles is no more than L. For a given convex polygon Q, Gewali et al [4]. addressed the guard placement problem on the exterior boundary that will cover the maximum area exterior to the polygon under L-visibility. They proposed a linear time algorithm for some given value of L. When the length L is greater than half of the perimeter, they declared that problem as open. Here we address that open problem and present an algorithm whose time complexity is linear in number of vertices of the polygon.
Fast Algorithms for Pseudoarboricity
2015
The densest subgraph problem, which asks for a subgraph with the maximum edges-to-vertices ratio d∗, is solvable in polynomial time. We discuss algorithms for this problem and the computation of a graph orientation with the lowest maximum indegree, which is equal to ⌈d∗⌉. This value also equals the pseudoarboricity of the graph. We show that it can be computed in O(|E| √ log log d∗) time, and that better estimates can be given for graph classes where d∗ satisfies certain asymptotic bounds. These runtimes are achieved by accelerating a binary search with an approximation scheme, and a runtime analysis of Dinitz’s algorithm on flow networks where all arcs, except the source and sink arcs, hav…