Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2015 | Book

Probabilistic Arguments in Graph Coloring (Invited Talk) Read chapter Read first chapter

Algorithms and Discrete Applied Mathematics

First International Conference, CALDAM 2015, Kanpur, India, February 8-10, 2015. Proceedings

Editors: Sumit Ganguly, Ramesh Krishnamurti

Publisher: Springer International Publishing

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book collects the refereed proceedings of the First International Conference onon Algorithms and Discrete Applied Mathematics, CALDAM 2015, held in Kanpur, India, in February 2015. The volume contains 26 full revised papers from 58 submissions along with 2 invited talks presented at the conference. The workshop covered a diverse range of topics on algorithms and discrete mathematics, including computational geometry, algorithms including approximation algorithms, graph theory and computational complexity.

Table of Contents

Frontmatter
Probabilistic Arguments in Graph Coloring (Invited Talk)
Abstract
Probabilistic arguments has come to be a powerful way to obtain bounds on various chromatic numbers. It plays an important role not only in obtaining upper bounds but also in establishing the tightness of these upper bounds. It often calls for the application of various (often simple) ideas, tools and techniques (from probability theory) like moments, concentration inequalities, known estimates on tail probabilities and various other probability estimates. A number of examples illustrate how this approach can be a very useful tool in obtaining chromatic bounds. For many of these bounds, no other approach for obtaining them is known so far. In this talk, we illustrate this approach with some specific applications to graph coloring. On the other hand, several specific applications of this approach have also motivated and led to the development of powerful tools for handling discrete probability spaces. An important tool (for establishing the tightness results) is the notion of random graphs. We do not necessarily present the best results (obtained using this approach) since the main purpose is to provide an introduction to the power and simplicity of the approach. Many of the examples and the results are already known and published in the literature and have also been improved further.
C. R. Subramanian

Approximation Algorithms

A PTAS for the Metric Case of the Minimum Sum-Requirement Communication Spanning Tree Problem
Abstract
This work considers the metric case of the minimum sum-requirement communication spanning tree problem (SROCT), which is an NP-hard particular case of the minimum communication spanning tree problem (OCT). Given an undirected graph G = (V,E) with non-negative lengths ω(e) associated to the edges satisfying the triangular inequality and non-negative routing weights r(u) associated to nodes u ∈ V, the objective is to find a spanning tree T of G, that minimizes: \(\frac{1}{2}\sum_{u\in V}\sum_{v\in V}\left(r(u)+r(v)\right)d(T,u,v)\), where d(H,x,y) is the minimum distance between nodes x and y in a graph H ⊆ G. We present a polynomial approximation scheme for the metric case of the SROCT improving the until now best existing approximation algorithm for this problem.
Santiago V. Ravelo, Carlos E. Ferreira
Constant Approximation for Broadcasting in k-cycle Graph
Abstract
Broadcasting is an information dissemination problem in a connected graph in which one vertex, called the originator, must distribute a message to all other vertices by placing a series of calls along the edges of the graph. Every time the informed vertices aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. The problem is NP-Complete for even more restricted classes of graphs, such as for 3-regular planar graphs. The best approximation algorithm for broadcast problem is \(O( \frac{\log(|V|)}{\log \log(|V|)}b(G))\). The polynomial time solvability is shown only for certain tree-like graphs; trees, unicyclic graphs, tree of cycles. The problem becomes very difficult when cycles intersect. In this paper we study the broadcast problem in a simple cactus graph called k-cycle graph. For any originator we present a (2 − ε)-approximation algorithm in the arbitrary k-cycle graph. We also prove that our algorithm generates the optimal broadcast time for some subclasses of this graph.
Puspal Bhabak, Hovhannes A. Harutyunyan

Computational Geometry

Three Paths to Point Placement
Abstract
The point placement problem is to determine the positions of a set of n distinct points, P = {p 1, p 2, p 3, …, p n }, on a line uniquely, up to translation and reflection, from the fewest possible distance queries between pairs of points. Each distance query corresponds to an edge in a graph, called point placement graph (ppg), whose vertex set is P. The uniqueness requirement of the placement translates to line rigidity of the ppg. In this paper, we show how to construct in 2 rounds a line rigid ppg of size 9n/7 + O(1). This improves the best known result of 4n/3 + O(1). We also improve the lower bound on 2-round algorithms from 14n/13 to 9n/8.
Md. Shafiul Alam, Asish Mukhopadhyay
Vertex Guarding in Weak Visibility Polygons
Abstract
The art gallery problem enquires about the least number of guards that are sufficient to ensure that an art gallery, represented by a polygon P, is fully guarded. In 1998, the problems of finding the minimum number of point guards, vertex guards, and edge guards required to guard P were shown to be APX-hard by Eidenbenz, Widmayer and Stamm. In 1987, Ghosh presented approximation algorithms for vertex guards and edge guards that achieved a ratio of \(\mathcal{O}(\log n)\), which was improved upto \(\mathcal{O}(\log\log OPT)\) by King and Kirkpatrick in 2011. It has been conjectured that constant-factor approximation algorithms exist for these problems. We settle the conjecture for the special class of polygons that are weakly visible from an edge and contain no holes by presenting a 6-approximation algorithm for finding the minimum number of vertex guards that runs in \(\mathcal{O}(n^2)\) time. On the other hand, for weak visibility polygons with holes, we present a reduction from the Set Cover problem to show that there cannot exist a polynomial time algorithm for the vertex guard problem with an approximation ratio better than \(((1−\epsilon)/12)\ln n\) for any ε > 0, unless NP = P.
Pritam Bhattacharya, Subir Kumar Ghosh, Bodhayan Roy
On Collections of Polygons Cuttable with a Segment Saw
Abstract
(I) Given a cuttable polygon P drawn on a piece of planar material Q, we show how to cut P out of Q by a (small) segment saw with a total length no more than 2.5 times the optimal. We revise the algorithm of Demaine et al. (2001) so as to achieve this ratio.
(II) We prove that any collection \(\mathcal{R}\) of n disjoint axis-parallel rectangles is cuttable by at most 4n rays and present an algorithm that runs in O(n logn) time for computing a suitable cutting sequence. In particular the same result holds for cutting with an arbitrary segment saw (of any length).
(III) In contrast, we show that there exist collections of disjoint rectangles (in arbitrary orientations) that are uncuttable by a segment saw. We also present various uncuttable collections of disjoint polygons, including triangles.
Adrian Dumitrescu, Anirban Ghosh, Masud Hasan
Rectilinear Path Problems in Restricted Memory Setup
Abstract
We study the rectilinear path problem in the presence of disjoint axis parallel rectangular obstacles in the in-place and read-only setup. The input to the problem is a set \(\cal R\) of n axis-parallel rectangular obstacles in \(I\!\!R^2\). We need to preprocess the members in \(\cal R\) such that the following query can be answered efficiently.
Path-Query(p,q): Given a pair of points p and q, report an axis-parallel path from p to q avoiding the obstacles in \(\cal R\).
In the read-only setup, we consider a restricted version of the Path-Query(p,q) problem, where the objective is to check the existence of an xy-monotone path between the given pair of points p and q avoiding the obstacles, and report it if such a path exists. Given O(s) extra space, the problem can be solved in \(O(\frac{n^2}{s}+n\log s+ M_s\log n)\) time, where M s is the time complexity for computing the median of n elements in read-only setup using O(s) extra space.
In the in-place setup, we preprocess the input rectangles in a data structure such that for any pair of query points p and q, the problem Path-Query(p,q) can be solved efficiently. The time complexities for the preprocessing and query are O(nlogn) and O(n 3/4 + χ) respectively, where χ is the number of links (bends) in the path. The extra space requirement for both preprocessing and query answering are O(1). We also show that among a set of unit square obstacles, there always exists a path of O(logn) links between a pair of query points. Here, we use a different in-place data structure with same preprocessing time complexity to answer the query in O(logn) time.
Binay K. Bhattacharya, Minati De, Anil Maheswari, Subhas C. Nandy, Sasanka Roy

Graph Theory

New Polynomial Case for Efficient Domination in P 6-free Graphs
Abstract
In a graph G, an efficient dominating set is a subset D of vertices such that D is an independent set and each vertex outside D has exactly one neighbor in D. The Efficient Dominating Set problem (EDS) asks for the existence of an efficient dominating set in a given graph G, and the Weighted Efficient Dominating Set problem (WEDS) asks for an efficient dominating set of minimum total weight in the given graph G with vertex weight function w on V(G). The (W)EDS is known to be NP-complete for P 7-free graphs, and is known to be polynomial time solvable for P 5-free graphs. However, the computational complexity of the (W)EDS problem is unknown for P 6-free graphs. In this paper, we show that the WEDS problem can be solved in polynomial time for a subclass of P 6-free graphs, namely (P 6, banner)-free graphs, where a banner is the graph obtained from a chordless cycle on four vertices by adding a vertex that has exactly one neighbor on the cycle.
T. Karthick
Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties
Abstract
We consider an extension of the triangular-distance Delaunay graphs (TD-Delaunay) on a set P of points in general position in the plane. In TD-Delaunay, the convex distance is defined by a fixed-oriented equilateral triangle ∇, and there is an edge between two points in P if and only if there is an empty homothet of ∇ having the two points on its boundary. We consider higher-order triangular-distance Delaunay graphs, namely k https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-14974-5_9/978-3-319-14974-5_9_IEq1_HTML.gif TD, which contains an edge between two points if the interior of the smallest homothet of ∇ having the two points on its boundary contains at most k points of P. We consider the connectivity, Hamiltonicity and perfect-matching admissibility of k https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-14974-5_9/978-3-319-14974-5_9_IEq2_HTML.gif TD. Finally we consider the problem of blocking the edges of k https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-14974-5_9/978-3-319-14974-5_9_IEq3_HTML.gif TD.
Ahmad Biniaz, Anil Maheshwari, Michiel Smid
Separator Theorems for Interval Graphs and Proper Interval Graphs
Abstract
C.L.Monma and V.K.Wei [1986, J. Comb. Theory, Ser-B, 41, 141-181] proposed a unified approach to characterize several subclasses of chordal graphs using clique separator. The characterizations so obtained are called separator theorems. Separator theorems play an important role in designing algorithms in subclasses of chordal graphs. In this paper, we obtain separator theorems for interval graphs and proper interval graphs, which are subclasses of chordal graphs, following the framework of Monma and Wei.
B. S. Panda
Bounds for the b-chromatic Number of Induced Subgraphs and G − e
Abstract
All graphs considered in this paper are simple, finite and undirected. Let G be a graph with vertex set V and edge set E. The order of G will be denoted by n and size (number of edges) by m. A b-coloring of a graph is a proper coloring of the vertices of G such that each color class contains a color dominating vertex (c.d.v.), that is, a vertex adjacent to at least one vertex of every other color class. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. A b-chromatic coloring of G denotes a b-coloring using b(G) colors. From the definition of χ(G), we observe that each color class of a χ-coloring contains a c.d.v. Thus ω(G) ≤ χ(G) ≤ b(G), where ω(G) is the size of a maximum clique of G.
P. Francis, S. Francis Raj
New Characterizations of Proper Interval Bigraphs and Proper Circular Arc Bigraphs
Abstract
An interval bigraph B is a proper interval bigraph if there is an interval representation of B such that no interval of the same partite set is properly contained in the other. Similarly a circular arc bigraph B is a proper circular arc bigraph if there is a circular arc representation of B such that no arc of the same partite set is properly contained in the other. In this paper, we characterize proper interval bigraphs and proper circular arc bigraphs using two linear orderings of their vertex set.
Ashok Kumar Das, Ritapa Chakraborty
On Spectra of Corona Graphs
Abstract
Product graphs have been gainfully used in literature to generate mathematical models of complex networks which inherit properties of real networks. Realizing the duplication phenomena imbibed in the definition of corona product of two graphs, we define corona graphs. Given a small simple connected graph which we call basic graph, corona graphs are defined by taking corona product of the basic graph iteratively. We calculate the possibility of having a node of degree k in any corona graph which lead to obtain degree distribution of corona graphs. We determine explicit formulae of eigenvalues, Laplacian eigenvalues and signless Laplacian eigenvalues of corona graphs when the basic graph is regular. Computable expressions of eigenvalues and signless Laplacian eigenvalues are also obtained when the basic graph is a star graph.
Rohan Sharma, Bibhas Adhikari, Abhishek Mishra
Axiomatic Characterization of the Median and Antimedian Functions on Cocktail-Party Graphs and Complete Graphs
Abstract
A median (antimedian) of a profile of vertices on a graph G is a vertex that minimizes (maximizes) the remoteness value, that is, the sum of the distances to the elements in the profile. The median (or antimedian) function has as output the set of medians (antimedians) of a profile. It is one of the basic models for the location of a desirable (or obnoxious) facility in a network. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper an axiomatic characterization is obtained for the median and antimedian functions on cocktail-party graphs. In addition a characterization of the antimedian function on complete graphs is presented.
Manoj Changat, Divya Sindhu Lekha, Henry Martyn Mulder, Ajitha R. Subhamathi
Tree Path Labeling of Hypergraphs – A Generalization of the Consecutive Ones Property
Abstract
Given a set system \(\mathcal{F} \subseteq\) (2 U  ∖ ∅ ) of a finite set U of cardinality n and a tree T of size n, does there exist at least one bijection φ:U → V(T) such that for each \(S \in \mathcal{F}\), the set {φ(x) |x ∈ S} is the vertex set of a path in T? Our main result is that the existence of such a bijection from U to V(T) is equivalent to the existence of a function \(\mathcal{l}\) from \(\mathcal{F}\) to the set of all paths in T such that for any three, not necessarily distinct, \(S_1, S_2, S_3 \in \mathcal{F}\), \(|S_1 \cap S_2 \cap S_3|=|\mathcal{l}(S_1) \cap \mathcal{l}(S_2) \cap \mathcal{l}(S_3)|\). \(\mathcal{l}\) is referred to as a tree path labeling of \(\mathcal{F}\).
N. S. Narayanaswamy, Anju Srinivasan
On a Special Class of Boxicity 2 Graphs
Abstract
We define and study a class of graphs, called 2-stab interval graphs (2SIG), with boxicity 2 which properly contains the class of interval graphs. A 2SIG is an axes-parallel rectangle intersection graph where the rectangles have unit height (that is, length of the side parallel to Y-axis) and intersects either of the two fixed lines, parallel to the X-axis, distance 1 + ε (0 < ε < 1) apart. Intuitively, 2SIG is a graph obtained by putting some edges between two interval graphs in a particular rule. It turns out that for these kind of graphs, the chromatic number of any of its induced subgraphs is bounded by twice of its (induced subgraph) clique number. This shows that the graph, even though not perfect, is not very far from it. Then we prove similar results for some subclasses of 2SIG and provide efficient algorithm for finding their clique number. We provide a matrix characterization for a subclass of 2SIG graph.
Sujoy Kumar Bhore, Dibyayan Chakraborty, Sandip Das, Sagnik Sen
Domination in Some Subclasses of Bipartite Graphs
Abstract
A set D ⊆ V is called a dominating set of G = (V,E) if |N G [v] ∩ D| ≥ 1 for all v ∈ V. The Minimum Domination problem is to find a dominating set of minimum cardinality of the input graph. In this paper, we study the Minimum Domination problem for star-convex bipartite graphs, circular-convex bipartite graphs and triad-convex bipartite graphs. It is known that the Minimum Domination Problem for a graph with n vertices can be approximated within ln n. However, we show that for any ε > 0, the Minimum Domination problem does not admit a (1 − ε)ln n-approximation algorithm for star-convex bipartite graphs with n vertices unless NP ⊆ DTIME(n O(loglogn)). On the positive side, we propose polynomial time algorithms for computing a minimum dominating set of circular-convex bipartite graphs and triad-convex bipartite graphs, by polynomially reducing the Minimum Domination problem for these graph classes to the Minimum Domination problem for convex bipartite graphs.
Arti Pandey, B. S. Panda

Computational Complexity

Parameterized Analogues of Probabilistic Computation
Abstract
We study structural aspects of randomized parameterized computation. We introduce a new class W[P]−PFPT as a natural parameterized analogue of PP. Our definition uses the machine based characterization of the parameterized complexity class W[P] obtained by Chen et.al [TCS 2005]. We translate most of the structural properties and characterizations of the class PP to the new class W[P]−PFPT.
We study a parameterization of the polynomial identity testing problem based on the degree of the polynomial computed by the arithmetic circuit. We obtain a parameterized analogue of the well known Schwartz-Zippel lemma [Schwartz, JACM 80 and Zippel, EUROSAM 79].
Additionally, we introduce a parameterized variant of permanent, and prove its #W[1] completeness.
Ankit Chauhan, B. V. Raghavendra Rao
Algebraic Expressions of Rhomboidal Graphs
Abstract
The paper investigates relationship between algebraic expressions and graphs. We consider rhomboidal non-series-parallel graphs, specifically, a digraph called a full square rhomboid. Our intention is to simplify the expressions of full square rhomboids. We describe two decomposition methods for generating expressions of rhomboidal graphs and carry out their comparative analysis.
Mark Korenblit
Solving Hamiltonian Cycle by an EPT Algorithm for a Non-sparse Parameter
Abstract
Many hard graph problems, such as Hamiltonian Cycle, become FPT when parameterized by treewidth, a parameter that is bounded only on sparse graphs. When parameterized by the more general parameter clique-width, Hamiltonian Cycle becomes W[1]-hard, as shown by Fomin et al. [5]. Sæther and Telle address this problem in their paper [14] by introducing a new parameter, split-matching-width, which lies between treewidth and clique-width in terms of generality. They show that even though graphs of restricted split-matching-width might be dense, solving problems such as Hamiltonian Cycle can be done in FPT time.
Recently, it was shown that Hamiltonian Cycle parameterized by treewidth is in EPT [1,6], meaning it can be solved in \(n^{\mathcal{O}(1)}2^{\mathcal{O}(k)}\)-time. In this paper, using tools from [6], we show that also parameterized by split-matching-width Hamiltonian Cycle is EPT. To the best of our knowledge, this is the first EPT algorithm for any ”globally constrained” graph problem parameterized by a non-trivial and non-sparse structural parameter. To accomplish this, we also give an algorithm constructing a branch decomposition approximating the minimum split-matching-width to within a constant factor. Combined, these results show that the algorithms in [14] for Edge Dominating Set, Chromatic Number and Max Cut all can be improved. We also show that for Hamiltonian Cycle and Max Cut the resulting algorithms are asymptotically optimal under the Exponential Time Hypothesis.
Sigve Hortemo Sæther

Algorithms

Associativity for Binary Parallel Processes: A Quantitative Study
Abstract
We investigate the common interpretation of parallel processes as computation trees. The basis for our approach is the combinatorics of increasingly labelled structures, and our main objective is to provide quantitative results relying on advanced analytic techniques. Unlike previous works, the combinatorial model we propose captures the following ingredients of the algebraic presentation : a binary parallel operator with associativity law. The switch from general trees to binary encodings in this paper makes everything more complex (but eventually workable). Ultimately, we provide a precise characterization and asymptotic approximations of various measures of parallel processes in the average case, especially the average size of the computation trees and their average number of paths, providing a more meaningful notion of combinatorial explosion than in the (rather trivial) worst-case. Beyond the measures, we also provide a precise characterization of the typical combinatorial shape of the computation trees, especially their level-decomposition, an interesting notion of process depth. From a more practical point of view, we develop efficient algorithms for the uniform random sampling of computations. Thanks to our typical shape analysis, it is possible to uniformly sample computation prefixes at a given depth in a very efficient way. Indeed, these algorithms work directly on the syntax trees of the processes and do not require the explicit construction of the state space, hence completely avoiding the combinatorial explosion.
Olivier Bodini, Antoine Genitrini, Frédéric Peschanski, Nicolas Rolin
A Tight Bound for Congestion of an Embedding
Abstract
Graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. Congestion is one of the main optimization objectives in global routing. In this paper, we introduce a technique to obtain a tight bound for congestion of an embedding. Moreover, we give algorithms to compute exact congestion of embedding the hypercubes into the cylinder and the torus and prove that the bound obtained is sharp.
Paul Manuel, Indra Rajasingh, R. Sundara Rajan, N. Parthiban, T. M. Rajalaxmi
Auction/Belief Propagation Algorithms for Constrained Assignment Problem
Abstract
In this paper, we investigate the constrained assignment problem: a set of offers are to be assigned to a set of customers. There are constraints on both the number of available copies for each offer and the number of offers one customer can get. To measure the assignment gain, we have a score for each customer-offer pair, quantifying how beneficial it is for assigning a customer an offer. Additionally, a customer can get at most one copy of the same offer and at most one offer from the same category (an offer is associated with a category in a taxonomy, for example bakery, dairy, and so on). The objective is to optimize the assignment so that the sum of scores (global benefits) are maximized. We developed an auction algorithm for this problem and proved both its correctness and convergence. To show its effectiveness and efficiency, we compared it with heuristic algorithms and one minimum cost flow algorithm (network simplex). To show its scalability, we ran test cases of size up to 200 offers × 3,000,000 customers on a 16GB machine, where most of the linear/integer programming tools would fail under this setting. Finally, we transformed the auction algorithm into an equivalent belief propagation algorithm, and provided another convergence case for belief propagation on a loopy graph with node constraints.
Mindi Yuan, Wei Shen, Jun Li, Yannis Pavlidis, Shen Li
Bi-directional Search for Skyline Probability
Abstract
Computing the skyline probability of an object for a database, wherein the probability of preferences between pairs of data objects are uncertain, requires computing the probability of union of events from the probabilities of all possible joint probabilities. From the literature it can be seen that for a database of size n it requires computation of 2 n joint probabilities of all possible combinations. All known algorithms for probabilistic skyline computation over uncertain preferences attempt to find inexact value of skyline probability by resorting to sampling or to approximation schemes. In this paper we use a concept called zero-contributing set of a power set lattice to denote portion of the lattice (a sub-lattice) such that the signed aggregate of joint probabilities corresponding to this set is zero. When such sets can be implicitly identified, the corresponding terms can be removed, saving substantial computational efforts. We propose an efficient heuristic that employs a bi-directional search traversing level wise the power set lattice from top and from bottom and prunes the exponential search space based on zero-contribution.
Arun K. Pujari, Venkateswara Rao Kagita, Anubhuti Garg, Vineet Padmanabhan
Cumulative Vehicle Routing Problem: A Column Generation Approach
Abstract
Cumulative vehicle routing problems are a simplified model of fuel consumption in vehicle routing problems. Here we study computationally, an approach for constructing approximate solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation, and is solved using column generation. The pricing sub-problem is solved using dynamic programming. Simulation results show that the simple scalable strategy computes solutions with cost close to the lower bound given by the linear programming relaxation.
Daya Ram Gaur, Rishi Ranjan Singh
Energy Efficient Sweep Coverage with Mobile and Static Sensors
Abstract
Sweep coverage provides solution for the applications in wireless sensor networks, where periodic monitoring is sufficient instead of continuous monitoring. For a given set of points in the plane, the objective of the sweep coverage problem is to minimize number of sensors required in order to guarantee sweep coverage for a given set of points of interest. Instead of using only mobile sensors for sweep coverage, use of both static and mobile sensors can be more effective in terms of energy utilization. In this paper we introduce the EEGSweep coverage problem, where objective is to minimize energy consumption by a set of sensors (mobile and/or static) with guaranteed sweep coverage for a given set of points. We prove that the EEGSweep coverage problem is NP-hard and cannot be approximated within a factor of 2. We propose an 8-approximation algorithm to solve the problem. A 2-approximation algorithm is also proposed for a special case of this problem.
Barun Gorain, Partha Sarathi Mandal
Generation of Random Digital Curves Using Combinatorial Techniques
Abstract
A fast linear-time algorithm to generate non-intersecting closed random orthogonal (4-connected) digital curves of finite length imposed on a background grid is proposed in this paper. A novel timestamp-based combinatorial technique is used so that the curve grows freely without intersecting itself. The combintaorial constraints are further modified to generate 8-connected digital curves. The time complexity of the algorithm is linear in length of the curve, as decisions are made locally based on current-neighbourhood points of the digital curve. The algorithm has been implemented and tested exhaustively and an analysis of the results is also presented.
Apurba Sarkar, Arindam Biswas, Mousumi Dutt, Arnab Bhattacharya
Backmatter
Metadata
Title
Algorithms and Discrete Applied Mathematics
Editors
Sumit Ganguly
Ramesh Krishnamurti
Copyright Year
2015
Publisher
Springer International Publishing
Electronic ISBN
978-3-319-14974-5
Print ISBN
978-3-319-14973-8
DOI
https://doi.org/10.1007/978-3-319-14974-5

Premium Partner

    Image Credits