University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 06 01 3-difference cordial labeling of some cycle related graphs 1 10 EN R. Ponraj Department of Mathematics, Sri Paramakalyani College,Alwarkurichi-627 412, India ponrajmaths@gmail.com M. Maria Adaickalam Department of Mathematics, Kamarajar Government Arts College, Surandai-627859, India mariaadaickalam@gmail.com Let <em>G</em> be a (<em>p</em>, <em>q</em>) graph. Let <em>k</em> be an integer with 2 ≤ <em>k</em> ≤ <em>p</em> and <em>f</em> from <em>V</em> (<em>G</em>) to the set {1, 2, . . . , <em>k</em>} be a map. For each edge <em>uv</em>, assign the label |<em>f</em>(<em>u</em>) − <em>f</em>(<em>v</em>)|. The function <em>f</em> is called a <em>k</em>-difference cordial labeling of <em>G</em> if |<em>ν<sub>f</sub></em> (<em>i</em>) − <em>v<sub>f</sub></em> (<em>j</em>)| ≤ 1 and |<em>e<sub>f</sub></em> (0) − <em>e<sub>f</sub></em> (1)| ≤ 1 where <em>v<sub>f</sub></em> (<em>x</em>) denotes the number of vertices labelled with <em>x</em> (<em>x</em> ∈ {1, 2 . . . , <em>k</em>}), <em>e<sub>f</sub></em> (1) and <em>e<sub>f</sub></em> (0) respectively denote the number of edges labelled with 1 and not labelled with 1. A graph with a <em>k</em>-difference cordial labeling is called a <em>k</em>-difference cordial graph. In this paper we investigate the 3-difference cordial labeling of wheel, helms, flower graph, sunflower graph, lotus inside a circle, closed helm, and double wheel. Path,cycle,Wheel,Star https://jac.ut.ac.ir/article_7927.html https://jac.ut.ac.ir/article_7927_2058a8520b6be55a66b6d88cf1ff676f.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 06 01 A Survey on Complexity of Integrity Parameter 11 19 EN Mahmood Shabankhah University of Tehran, College of Engineering, Department of Engineering Science shabankhah@ut.ac.ir Many graph theoretical parameters have been used to describe the vulnerability of communication networks, including toughness, binding number, rate of disruption, neighbor-connectivity, integrity, mean integrity, edgeconnectivity vector, l-connectivity and tenacity. In this paper we discuss Integrity and its properties in vulnerability calculation. The integrity of a graph <em>G</em>, <em>I</em>(<em>G</em>), is defined to be min(| <em>S</em> | +<em>m</em>(<em>G</em> −<em> S</em>)) where <em>S</em> ⊂ <em>V</em> (<em>G</em>) and <em>m</em>(<em>G</em> − <em>S</em>) is the maximum order of the components of <em>G</em> − <em>S</em>. Similarly the edge-integrity of <em>G</em> is <em>I′</em>(<em>G</em>) := min(| <em>S</em> | +<em>m</em>(<em>G</em> − <em>S</em>)) where now <em>S</em> ⊆ <em>E</em>(<em>G</em>). Here and through the remaining sections, by an <em>I</em>-set (with respect to some prescribed graph <em>G</em>) we will mean a set <em>S</em> ⊂ <em>V</em> (<em>G</em>) for which <em>I</em>(<em>G</em>) =| <em>S</em> | +<em>m</em>(<em>G</em> − <em>S</em>). We define an<em> I′</em>-set similarly. <br />In this paper we show a lower bound on the edgeintegrity of graphs and present an algorithm for its computation. Integrity parameter,toughness,neighborconnectivity,mean integrity,edge-connectivity vector,l-connectivity and tenacity https://jac.ut.ac.ir/article_7931.html https://jac.ut.ac.ir/article_7931_cbdf47ab50798add111a36ddb52c43be.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 06 02 On Generalized Weak Structures 21 26 EN R. Jamunarani Research Center, Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur-628 215, Tamil Nadu, India jamunarani1977@gmail.com P. Jeyanthi Research Center, Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur-628 215, Tamil Nadu, India jeyajeyanthi@rediffmail.com T. Noiri Shiokota-cho Hinagu, Yatsushiro-shi kumamoto-ken, 869-5142 Japan t.noiri@nifty.com Avila and Molina  introduced the notion of generalized weak structures which naturally generalize minimal structures, generalized topologies and weak structures and the structures <em>α </em>(<em>g</em>),<em>π</em>(<em>g</em>),<em>σ</em>(<em>g</em>) and <em>β</em> (<em>g</em>). This work is a further investigation of generalized weak structures due to Avila and Molina. Further we introduce the structures <em>ro</em>(<em>g</em>) and <em>rc</em>(<em>g</em>) and study the properties of the structures <em>ro</em>(<em>g</em>), <em>rc</em>(<em>g</em>), and also further properties of <em>α </em>(<em>g</em>),<em>π</em>(<em>g</em>),<em>σ</em>(<em>g</em>) and <em>β</em> (<em>g</em>) due to . Generalized weak structure,ro(g),rc(g),α (g),π(g),σ(g),β (g) https://jac.ut.ac.ir/article_7932.html https://jac.ut.ac.ir/article_7932_9e73174a81cdfca4a7d711bd908dca2a.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 06 01 Online Scheduling of Jobs for D-benevolent instances On Identical Machines 27 36 EN I. Mohammadi University of Tehran, Department of Algorithms and Computation. mohammadi.iman@alumni.ut.ac.ir Dara Moazzami University of Tehran, College of Engineering, Faculty of Engineering Science dmoazzami@ut.ac.ir We consider online scheduling of jobs with speci c release time on <em>m</em> identical machines. Each job has a weight and a size; the goal is maximizing total weight of completed jobs. At release time of a job it must immediately be scheduled on a machine or it will be rejected. It is also allowed during execution of a job to preempt it; however, it will be lost and only weight of completed jobs contribute on pro t of the algorithm. In this paper we study <em>D</em>-benevolent instances which is a wide and standard class and we give a new algorithm, that admits (2<em>m</em> + 4)-competitive ratio. It is almost half of the previous known upper bound for this problem. Online Algorithms Scheduling Identical Machine,Upper bound https://jac.ut.ac.ir/article_7933.html https://jac.ut.ac.ir/article_7933_f66b689563341f19f8abe5d5de8da400.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 06 01 Mixed cycle-E-super magic decomposition of complete bipartite graphs 37 52 EN G. Marimuthu Department of Mathematics, The Madura College, Madurai -625 011, Tamilnadu, India yellowmuthu@yahoo.com; S. Stalin Kumar Department of Mathematics, The American College, Madurai - 625 002, Tamilnadu,India sskumbas@gmail.com An H-magic labeling in a <em>H</em>-decomposable graph <em>G</em> is a bijection<em> f</em> : <em>V</em> (<em>G</em>) ∪ <em>E</em>(<em>G</em>) → {1, 2, ..., <em>p</em> + <em>q</em>} such that for every copy <em>H</em> in the decomposition, Σ<sub><em>ν</em>ε<em>V</em>(<em>H</em>)</sub> <em>f</em>(<em>v</em>) +  Σ<sub><em>e</em>ε<em>E</em>(<em>H</em>)</sub> <em>f</em>(<em>e</em>) is constant. <em>f</em> is said to be <em>H</em>-<em>E</em>-super magic if <em>f</em>(<em>E</em>(<em>G</em>)) = {1, 2, · · · , <em>q</em>}. A family of subgraphs <em>H</em><sub>1</sub>,<em>H</em><sub>2</sub>, · · · ,<em>H<sub>h</sub></em> of <em>G</em> is a mixed cycle-decomposition of <em>G</em> if every subgraph <em>H<sub>i</sub></em> is isomorphic to some cycle<em> C<sub>k</sub></em>, for <em>k</em> ≥ 3, <em>E</em>(<em>H<sub>i</sub></em>) ∩ <em>E</em>(<em>H<sub>j</sub></em>) = ∅ for <em>i</em> ≠<em> j</em> and ∪<em><sup>h</sup></em><sub><em>i</em>=1</sub><em>E</em>(<em>H<sub>i</sub></em>) = <em>E</em>(<em>G</em>). In this paper, we prove that <em>K</em><sub>2<em>m</em>,2<em>n</em></sub> is mixed cycle-E-super magic decomposable where <em>m</em> ≥ 2, <em>n</em> ≥ 3, with the help of the results found in . H-decomposable graph,H-E-super magic labeling,mixed cycle-E-super magic decomposable graph https://jac.ut.ac.ir/article_7934.html https://jac.ut.ac.ir/article_7934_5f537569fcfee7d3d929abdef859d33f.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 03 19 Heuristic and exact algorithms for Generalized Bin Covering Problem 53 62 EN S. Jabari University of Tehran, Department of Algorithms and Computation. sjabari@ut.ac.ir Dara Moazzami University of Tehran, College of Engineering, Faculty of Engineering Science dmoazzami@ut.ac.ir A. Ghodousian University of Tehran, College of Engineering, Faculty of Engineering Science a.ghodousian@ut.ac.ir In this paper, we study the Generalized Bin Covering problem. For this problem an exact algorithm is introduced which can nd optimal solution for small scale instances. To nd a solution near optimal for large scale instances, a heuristic algorithm has been proposed. By computational experiments, the eciency of the heuristic algorithm is assessed. Generalized Bin Covering Problem,heuristic algorithm,greedy algorithm https://jac.ut.ac.ir/article_7936.html https://jac.ut.ac.ir/article_7936_ead5452fc8136548321a56c8bfa77888.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 06 10 Zarankiewicz Numbers and Bipartite Ramsey Numbers 63 78 EN Alex F. Collins Rochester Institute of Technology, School of Mathematical Sciences, Rochester, NY 14623 weincoll@gmail.com Alexander W. N. Riasanovsky University of Pennsylvania, Department of Mathematics, Philadelphia, PA 19104, USA alexneal@math.upenn.edu John C. Wallace Trinity College, Department of Mathematics, Hartford, CT 06106, USA john.wallace@trincoll.edu Stanis law P. Radziszowski Rochester Institute of Technology, Department of Computer Science, Rochester, NY 14623 spr@cs.rit.edu The Zarankiewicz number <em>z</em>(<em>b;</em> <em>s</em>) is the maximum size of a subgraph of <em>K</em><sub><em>b</em>,<em>b</em></sub> which does not contain <em>K</em><sub><em>s</em>,<em>s</em></sub> as a subgraph. The two-color bipartite Ramsey number <em>b</em>(<em>s</em>, <em>t</em>) is the smallest integer <em>b</em> such that any coloring of the edges of <em>K</em><sub><em>b</em>,<em>b</em></sub> with two colors contains a <em>K</em><sub><em>s</em>,<em>s</em></sub> in the rst color or a <em>K</em><sub><em>t</em>,<em>t</em></sub> in the second color.<br />In this work, we design and exploit a computational method for bounding and computing Zarankiewicz numbers. Using it, we obtain several new values and bounds on <em>z</em>(<em>b;</em> <em>s</em>) for 3≤s≤6. Our approach and new knowledge about <em>z</em>(<em>b;</em> <em>s</em>) permit us to improve some of the results on bipartite Ramsey numbers obtained by Zarankiewicz number,bipartite Ramsey number https://jac.ut.ac.ir/article_7943.html https://jac.ut.ac.ir/article_7943_0d5d2a7f40f78dfe0e529df98f3049dd.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 04 01 Randomized Algorithm For 3-Set Splitting Problem and it's Markovian Model 79 92 EN Mahdi Heidari Department of Algorithms and Computation, University of Tehran mahdi.heydari@intec.ugent.be Ali Golshani Department of Algorithms and Computation, University of Tehran ali.golshani@gmail.com D. Moazzami University of Tehran, College of Engineering, Faculty of Enginering Science dmoazzami@ut.ac.ir Ali Moeini University of Tehran, College of Engineering, Faculty of Enginering Science moeini@ut.ac.ir In this paper we restrict every set splitting problem to the special case in which every set has just three elements. This restricted version is also NP-complete. Then, we introduce a general conversion from any set splitting problem to 3-set splitting. Then we introduce a randomize algorithm, and we use Markov chain model for run time complexity analysis of this algorithm. In the last section of this paper we introduce "Fast Split" algorithm. NP-complete problem,set splitting problem,SAT problem,Markov chain https://jac.ut.ac.ir/article_7944.html https://jac.ut.ac.ir/article_7944_cf76fdb4b0ab6812faebfef5f611d4d6.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 03 24 A Cellular Automaton Based Algorithm for Mobile Sensor Gathering 93 99 EN S. Saadatmand University of New South Wales, College of Engineering, Department of Computer Science, Sydney, Australia. samadseadatmand@yahoo.com D. Moazzami University of Tehran, College of Engineering, Faculty of Engineering Science dmoazzami@ut.ac.ir A. Moeini University of Tehran, College of Engineering, Faculty of Engineering Science moeini@ut.ac.ir In this paper we proposed a Cellular Automaton based local algorithm to solve the autonomously sensor gathering problem in Mobile Wireless Sensor Networks (MWSN). In this problem initially the connected mobile sensors deployed in the network and goal is gather all sensors into one location. The sensors decide to move only based on their local information. Cellular Automaton (CA) as dynamical systems in which space and time are discrete and rules are local, is proper candidate to simulate and analyze the problem. Using CA presents a better understanding of the problem. Mobile Wireless Sensor Network,Mobile Sensor Gathering,Cellular Automata,Local Algorithm https://jac.ut.ac.ir/article_7947.html https://jac.ut.ac.ir/article_7947_1aea8cc39be37b7a09b0e9f9f6aa0812.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 04 01 A Mathematical Optimization Model for Solving Minimum Ordering Problem with Constraint Analysis and some Generalizations 101 117 EN Samira Rezaei Department of Algorithms and Computation, University of Tehran samirarezaei@ut.ac.ir Amin Ghodousian University of Tehran, College of Engineering, Faculty of Engineering Science a.ghodousian@ut.ac.ir In this paper, a mathematical method is proposed to formulate a generalized ordering problem. This model is formed as a linear optimization model in which some variables are binary. The constraints of the problem have been analyzed with the emphasis on the assessment of their importance in the formulation. On the one hand, these constraints enforce conditions on an arbitrary subgraph and then give sufficient conditions for feasibility, on the other hand, they provide a natural way to generalize the applied aspects of the model without increasing the number of the binary variables. linear programming,integer programming,minimum ordering https://jac.ut.ac.ir/article_7949.html https://jac.ut.ac.ir/article_7949_b3e9bb57657183c34d60a4df9921c654.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 05 01 The edge tenacity of a split graph 119 125 EN Bahareh Bafandeh Mayvan Department of Computer Engineering, Ferdowsi University of Mashhad bahareh.bafandeh@gmail.com The edge tenacity T<sub><em>e</em></sub>(<em>G</em>) of a graph <em>G</em> is de ned as:<br />T<sub><em>e</em></sub>(G) = min {[|<em>X</em>|+<em>τ</em>(<em>G</em>-<em>X</em>)]/[<em>ω</em>(<em>G</em>-<em>X</em>)-1]|<em>X</em> <span>⊆</span><span><em> E</em>(<em>G</em>) and<em> ω</em>(<em>G</em>-<em>X</em>) > 1}</span> <br />where the minimum is taken over every edge-cutset <em>X</em> that separates <em>G</em> into <em>ω</em>(<em>G</em> - <em>X</em>) components, and by <em>τ</em>(<em>G</em> -<em> X</em>) we denote the order of a largest component of <em>G</em>. The objective of this paper is to determine this quantity for split graphs. Let <em>G</em> = (<em>Z</em>; <em>I</em>; <em>E</em>) be a noncomplete connected split graph with minimum vertex degree <em>δ</em>(<em>G</em>) we prove that if <em>δ</em>(<em>G</em>)≥|<em>E</em>(<em>G)</em>|/[|<em>V</em>(<em>G</em>)|-1]  then its edge-tenacity is |<em>E</em>(<em>G)</em>|/[|<em>V</em>(<em>G</em>)|-1] . Vertex degree,split graphs,edge tenacity https://jac.ut.ac.ir/article_7950.html https://jac.ut.ac.ir/article_7950_79987a74d7a89e4dc593ea40d6df17ea.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 47 1 2016 05 21 Minimum Tenacity of Toroidal graphs 127 135 EN Hamid Doost Hosseini University of Tehran, College of Engineering, School of Civil Engineering h.doosth@gmail.com The tenacity of a graph <em>G</em>,<em> T</em>(<em>G</em>), is de ned by <em>T</em>(<em>G</em>) = min{[|<em>S</em>|+<em>τ</em>(<em>G</em>-<em>S</em>)]/[<em>ω</em>(<em>G</em>-<em>S</em>)]}, where the minimum is taken over all vertex cutsets<em> S</em> of <em>G</em>. We de ne <em>τ</em>(<em>G</em> - <em>S</em>) to be the number of the vertices in the largest component of the graph <em>G</em> -<em> S</em>, and <em>ω</em>(<em>G</em> - <em>S</em>) be the number of components of <em>G</em> - <em>S</em>.In this paper a lower bound for the tenacity <em>T</em>(<em>G</em>) of a graph with genus <em>γ</em>(<em>G</em>) is obtained using the graph's connectivity <em>κ</em>(<em>G</em>). Then we show that such a bound for almost all toroidal graphs is best possible. genus,graph's connectivity,toroidal graphs https://jac.ut.ac.ir/article_7951.html https://jac.ut.ac.ir/article_7951_c8ea937acc51627d689d94f03167568d.pdf