368 results
Search Results
2. The number of affine equivalent classes and extended affine equivalent classes of vectorial Boolean functions
- Author
-
Xi Chen, Longjiang Qu, Chao Li, and Shaojing Fu
- Subjects
Discrete mathematics ,Group isomorphism ,Applied Mathematics ,Open problem ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Upper and lower bounds ,010201 computation theory & mathematics ,Logic gate ,Discrete Mathematics and Combinatorics ,Affine transformation ,Boolean function ,Focus (optics) ,Mathematics ,Variable (mathematics) - Abstract
Affine equivalent classes and extended affine equivalent (EA-equivalent for short) classes of vectorial Boolean functions have important applications in cryptography, logic circuit, sequences for communications, etc. Recently, Y. Zhang et al., computed the number of affine equivalent classes of n -variable Boolean functions when 1 ≤ n ≤ 10 by group isomorphism (Zhang et al., 2016). However, the case for affine equivalent vectorial Boolean function remains a challenging open problem. Furthermore, little result for EA-equivalent vectorial Boolean function is known except a trivial lower bound mentioned in Mullen and Panario (2013, P246). In this paper, we focus on the challenging problem of calculating the number of affine equivalent classes and EA-equivalent classes of vectorial Boolean functions. First, for EA-equivalence, we prove that the trivial lower bound proposed in Mullen and Panario (2013) has at least 3 effective figures if n is not too small. We then show that the lower bound also holds for affine equivalent classes. Furthermore, we give an explicit formula and calculate the exact number of affine equivalent classes of ( n , m ) -functions with 1 ≤ m , n ≤ 11 by GAP. The results in this paper are helpful for the theory and applications of the classifications of vectorial Boolean functions.
- Published
- 2021
3. On partial cubes, well-graded families and their duals with some applications in graphs
- Author
-
Alireza Mofidi
- Subjects
Structure (mathematical logic) ,Discrete mathematics ,Lemma (mathematics) ,05C75, 05C65, 05D05, 05C20, 03C45 ,Applied Mathematics ,Duality (mathematics) ,0211 other engineering and technologies ,021107 urban & regional planning ,Context (language use) ,Mathematics - Logic ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Domain (mathematical analysis) ,Set (abstract data type) ,010201 computation theory & mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Dual polyhedron ,Combinatorics (math.CO) ,Logic (math.LO) ,Finite set ,Mathematics - Abstract
Well-graded families, extremal systems and maximum systems (the last two in the sense of VC-theory and Sauer-Shelah lemma on VC-dimension) are three important classes of set systems. This paper aims to study the notion of duality in the context of these classes of set systems and then use the obtained results for studying graphs. More specifically, we are concerned with the characterization of the finite set systems which themselves and their dual systems are both well-graded, extremal or maximum. On the way to this goal, and maybe also of independent interest, we study the structure of the well-graded families with the property that the size of the system is not much bigger than the size of its essential domain, that is, the set of elements of the domain which are shattered by the system as single element subsets. As another target of the paper, we use the above results to characterize graphs whose set systems of open or closed neighbourhoods, cliques or independent sets are well-graded, extremal or maximum. We clarify the relation of such graphs to the celebrated half-graphs. Through the paper, we frequently relate our investigations to the VC-dimension of the systems. Also we use one-inclusion graphs associated to set systems as an important technical tool., Comment: 32 pages
- Published
- 2020
4. Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity
- Author
-
Sihong Su and Jingjing Li
- Subjects
Discrete mathematics ,Degree (graph theory) ,Applied Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Nonlinear system ,Integer ,010201 computation theory & mathematics ,Algebraic immunity ,Discrete Mathematics and Combinatorics ,Algebraic number ,Boolean function ,Mathematics - Abstract
In this paper, we firstly introduce a kind of weightwise almost perfectly balanced Boolean functions. And then, a construction of weightwise perfectly balanced Boolean functions on 2 q + 2 variables is given by modifying the support of the weightwise almost perfectly balanced functions, where q is a non-negative integer. The algebraic degree, the weightwise nonlinearity, and the algebraic immunity of the newly constructed weightwise perfectly balanced functions are discussed at the end of this paper.
- Published
- 2020
5. A 4-approximation algorithm for the TSP-Path satisfying a biased triangle inequality
- Author
-
Usha Mohan, Sivaramakrishnan Ramani, and Sounaka Mishra
- Subjects
Discrete mathematics ,Triangle inequality ,Applied Mathematics ,0211 other engineering and technologies ,Approximation algorithm ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,01 natural sciences ,Travelling salesman problem ,Constant factor ,010201 computation theory & mathematics ,Path (graph theory) ,Discrete Mathematics and Combinatorics ,Enhanced Data Rates for GSM Evolution ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
In this paper, we study the path version of the Traveling Salesman Problem with the edge cost function satisfying a “relaxed” form of triangle inequality called the biased triangle inequality. We denote this problem as the Biased-TSP-Path . In this paper, we prove that the Biased-TSP-Path is approximable within a constant factor. Specifically, we design a 4-approximation algorithm by a suitable modification of the double-tree algorithm using effective shortcutting procedures.
- Published
- 2019
6. On one extension of Dirac’s theorem on Hamiltonicity
- Author
-
Didem Gözüpek, Mordechai Shalom, Yasemin Büyükçolak, and Sibel Özkan
- Subjects
Factor-critical graph ,Discrete mathematics ,021103 operations research ,Applied Mathematics ,0211 other engineering and technologies ,Quartic graph ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Combinatorics ,010201 computation theory & mathematics ,Graph power ,Graph minor ,Discrete Mathematics and Combinatorics ,Cubic graph ,Bound graph ,Regular graph ,Complement graph ,Mathematics - Abstract
The classical Dirac theorem asserts that every graph G on n ≥ 3 vertices with minimum degree δ ( G ) ≥ ⌈ n ∕ 2 ⌉ is Hamiltonian. The lower bound of ⌈ n ∕ 2 ⌉ on the minimum degree of a graph is tight. In this paper, we extend the classical Dirac theorem to the case where δ ( G ) ≥ ⌊ n ∕ 2 ⌋ by identifying the only non-Hamiltonian graph families in this case. We first present a short and simple proof. We then provide an alternative proof that is constructive and self-contained. Consequently, we provide a polynomial-time algorithm that constructs a Hamiltonian cycle, if exists, of a graph G with δ ( G ) ≥ ⌊ n ∕ 2 ⌋ , or determines that the graph is non-Hamiltonian. Finally, we present a self-contained proof for our algorithm which provides insight into the structure of Hamiltonian cycles when δ ( G ) ≥ ⌊ n ∕ 2 ⌋ and is promising for extending the results of this paper to the cases with smaller degree bounds.
- Published
- 2019
7. Optimal FHSs and DSSs via near zero-difference balanced functions
- Author
-
Xiwang Cao, Shanding Xu, Guangkui Xu, and Chunming Tang
- Subjects
Discrete mathematics ,Applied Mathematics ,Zero (complex analysis) ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,Direct-sequence spread spectrum ,Composition (combinatorics) ,01 natural sciences ,Connection (mathematics) ,Integer ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Order (group theory) ,Partition (number theory) ,Mathematics - Abstract
Zero-difference balanced (ZDB) functions were introduced by Ding in connection with constructions of optimal constant composition codes and optimal and perfect difference systems of sets. Based on such functions, people have constructed optimal constant weight codes and optimal frequency-hopping sequences. In order to obtain more optimal cryptographic objects, the zero-difference balanced (ZDB) function is generalized to the near zero-difference balanced (N-ZDB) function in the present paper, whose characterizations are partially given. Furthermore, we prove that near zero-difference balanced (N-ZDB) functions are equivalent to partitioned almost difference families (PADFs) in design theory. As the main contribution of this paper, three classes of the N-ZDB functions are proposed by means of the partition of Z n , where n is an odd positive integer. Employing these N-ZDB functions, we obtain at the same time optimal frequency-hopping sequences and optimal difference systems of sets with flexible parameters.
- Published
- 2018
8. A class of three-weight and five-weight linear codes
- Author
-
Dongdai Lin, Fei Li, and Qiuyan Wang
- Subjects
FOS: Computer and information sciences ,Discrete mathematics ,Class (set theory) ,business.industry ,Computer Science - Information Theory ,Information Theory (cs.IT) ,Applied Mathematics ,020206 networking & telecommunications ,94B05, 94B60 ,0102 computer and information sciences ,02 engineering and technology ,Communications system ,01 natural sciences ,Linear code ,Secret sharing ,Prime (order theory) ,Finite field ,010201 computation theory & mathematics ,Weight distribution ,Computer data storage ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,business ,Mathematics - Abstract
Recently, linear codes with few weights have been widely studied, since they have applications in data storage systems, communication systems and consumer electronics. In this paper, we present a class of three-weight and five-weight linear codes over Fp, where p is an odd prime and Fp denotes a finite field with p elements. The weight distributions of the linear codes constructed in this paper are also settled. Moreover, the linear codes illustrated in the paper may have applications in secret sharing schemes., Comment: 19 pages
- Published
- 2018
9. Tractability, hardness, and kernelization lower bound for and/or graph solution
- Author
-
Uéverton S. Souza and Fábio Protti
- Subjects
Discrete mathematics ,021103 operations research ,Applied Mathematics ,0211 other engineering and technologies ,Vertex cover ,Neighbourhood (graph theory) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Edge cover ,Vertex (geometry) ,Combinatorics ,Computer Science::Discrete Mathematics ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Induced subgraph isomorphism problem ,Bound graph ,Feedback vertex set ,Graph factorization ,Mathematics - Abstract
And/or graphs are well-known data structures with several applications in many fields of computer science, such as Artificial Intelligence, Distributed Systems, Software Engineering, and Operations Research. An and/or graph is an acyclic digraph G containing a single source vertex s , where every vertex v ∈ V ( G ) has a label f ( v ) ∈ { and,or }. In an and/or graph, (weighted) edges represent dependency relations between vertices: a vertex labeled and depends on all of its out-neighbors, while a vertex labeled or depends on only one of its out-neighbors. A solution subgraph H of an and/or graph G is a subdigraph of G containing its source vertex and such that if an and -vertex (resp. or -vertex) is included in H then all (resp. one) of its out-edges must also be included in H . In general, solution subgraphs represent feasible solutions of problems modeled by and/or graphs. The optimization problem associated with an and/or graph G consists of finding a minimum weight solution subgraph H of G , where the weight of a solution subgraph is the sum of the weights of its edges. Because of its wide applicability, in this work we develop a multivariate investigation of this optimization problem. In a previous paper (Souza et al., 2013) we have analyzed the complexity of such a problem under various aspects, including parameterized versions of it. However, the main open question has remained open: Is the problem of finding a solution subgraph of weight at most k (where k is the parameter) in FPT? In this paper we answer negatively to this question, proving the W[1]-hardness of the problem, and its W[P]-completeness when zero-weight edges are allowed. We also show that the problem is fixed-parameter tractable when parameterized by the tree-width, but it is W[SAT]-hard with respect to the clique-width and k as aggregated parameters. In addition, we show that when the out-edges of each or -vertex have all the same weight (a condition very common in practice), the problem becomes fixed-parameter tractable by the clique-width. Finally, using a framework developed by Bodlaender et al. (2009) and Fortnow and Santhanam (2011), based upon the notion of compositionality, we show that the tractable cases do not admit a polynomial kernel unless NP ⊆ coNP∕poly , even restricted to instances without or -vertices with out-degree greater than two.
- Published
- 2017
10. Linear kernels for k-tuple and liar’s domination in bounded genus graphs
- Author
-
Arijit Ghosh, Subhabrata Paul, and Arijit Bishnu
- Subjects
Discrete mathematics ,Domination analysis ,Applied Mathematics ,010102 general mathematics ,Parameterized complexity ,0102 computer and information sciences ,01 natural sciences ,Planar graph ,Combinatorics ,symbols.namesake ,010201 computation theory & mathematics ,Dominating set ,Kernelization ,Bounded function ,symbols ,Discrete Mathematics and Combinatorics ,Direct proof ,0101 mathematics ,Tuple ,Mathematics - Abstract
A set D ⊆ V is called a k -tuple dominating set of a graph G = ( V , E ) if | N G [ v ] ∩ D | ≥ k for all v ∈ V , where N G [ v ] denotes the closed neighborhood of v . A set D ⊆ V is called a liar’s dominating set of a graph G = ( V , E ) if (i) | N G [ v ] ∩ D | ≥ 2 for all v ∈ V and (ii) for every pair of distinct vertices u , v ∈ V , | ( N G [ u ] ∪ N G [ v ] ) ∩ D | ≥ 3 . Given a graph G , the decision versions of k - Tuple Domination Problem and the Liar’s Domination Problem are to check whether there exist a k -tuple dominating set and a liar’s dominating set of G of a given cardinality, respectively. These two problems are known to be NP -complete (Liao and Chang, 2003; Slater, 2009). In this paper, we study the parameterized complexity of these problems. We show that the k - Tuple Domination Problem and the Liar’s Domination Problem are W[2] -hard for general graphs. It can be verified that both the problems have a finite integer index and satisfy certain coverability property. Hence they admit linear kernel as per the meta-theorem in Bodlaender (2009), but the meta-theorem says nothing about the constant. In this paper, we present a direct proof of the existence of linear kernel with small constants for both the problems.
- Published
- 2017
11. Characterizations of (4K1, C4, C5)-free graphs
- Author
-
Dallas J. Fraser, Tom P. LaMantia, Chính T. Hoàng, Angèle M. Hamel, and Kevin Holmes
- Subjects
Block graph ,Discrete mathematics ,Clique-sum ,Applied Mathematics ,0102 computer and information sciences ,02 engineering and technology ,16. Peace & justice ,01 natural sciences ,Combinatorics ,Indifference graph ,020303 mechanical engineering & transports ,0203 mechanical engineering ,010201 computation theory & mathematics ,Chordal graph ,Partial k-tree ,Discrete Mathematics and Combinatorics ,Cograph ,Split graph ,Forbidden graph characterization ,Mathematics - Abstract
Given a set L of graphs, a graph G is L -free if G does not contain any graph in L as an induced subgraph. There has been keen interest in colouring graphs whose forbidden list L contains graphs with four vertices. A recent paper of Lozin and Malyshev (in press) discusses the state of the art on this problem, identifying three outstanding classes: L = ( 4 K 1 , claw ) , L = ( 4 K 1 , claw, co-diamond ) , and L = ( 4 K 1 , C 4 ) . In this paper we investigate the class of ( 4 K 1 , C 4 , C 5 )-free graphs and show that if G is a ( 4 K 1 , C 4 , C 5 )-free graph, then G either has bounded clique width or is perfect.
- Published
- 2017
12. Vertex-colouring of 3-chromatic circulant graphs
- Author
-
Ugo Pietropaoli and Sara Nicoloso
- Subjects
Discrete mathematics ,Applied Mathematics ,Neighbourhood (graph theory) ,Chromatic number ,020206 networking & telecommunications ,Circulant graphs ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Graph ,Vertex (geometry) ,Combinatorics ,Vertex-colouring ,Circulant graph ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Chromatic scale ,Circulant matrix ,Mathematics - Abstract
A circulant graph C n ( a 1 , … , a k ) is a graph with n vertices { v 0 , … , v n − 1 } such that each vertex v i is adjacent to vertices v ( i + a j ) m o d n , for j = 1 , … , k . In this paper we investigate the vertex colouring problem on circulant graphs. We approach the problem in a purely combinatorial way based on an array representation and propose an exact O ( k 3 log 2 n + n ) algorithm for a subclass of 3-chromatic C n ( a 1 , … , a k ) ’s with k ≥ 2 , which are characterized in the paper.
- Published
- 2017
13. Parametric bisubmodular function minimization and its associated signed ring family
- Author
-
Satoru Fujishige
- Subjects
Discrete mathematics ,021103 operations research ,Signed poset ,Applied Mathematics ,Minimization problem ,0211 other engineering and technologies ,Parameterized complexity ,Function minimization ,Principal partition ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Submodular set function ,Combinatorics ,Computer Science::Discrete Mathematics ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Partition (number theory) ,Partially ordered set ,Bisubmodular function ,Signed ring family ,Parametric statistics ,Mathematics - Abstract
The present paper shows an extension of the theory of principal partitions for submodular functions to that for bisubmodular functions. We examine the structure of the collection of all solutions of a parametric minimization problem described by a bisubmodular function and two vectors. The bisubmodular function to be minimized for each parameter is the sum of the bisubmodular function and a parameterized box-bisubmodular function given in terms of the two vectors. We show that the collection of all the minimizers for all parameters forms a signed ring family and it thus induces a signed poset on a signed partition of the underlying set. We further examine the structure of the signed ring family and reveal the decomposition structure depending on critical values of the parameter. Moreover, we discuss the relation between the results of this paper on bisubmodular functions and the theory of principal partitions developed for submodular functions.
- Published
- 2017
14. Further results on the deficiency of graphs
- Author
-
Petros A. Petrosyan and Hrant Khachatrian
- Subjects
Vertex (graph theory) ,Discrete mathematics ,Applied Mathematics ,Complete graph ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Graph ,Combinatorics ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Mathematics - Abstract
A proper t -edge-coloring of a graph G is a mapping α : E ( G ) → { 1 , … , t } such that all colors are used, and α ( e ) ≠ α ( e ′ ) for every pair of adjacent edges e , e ′ ∈ E ( G ) . If α is a proper edge-coloring of a graph G and v ∈ V ( G ) , then the spectrum of a vertex v , denoted by S ( v , α ) , is the set of all colors appearing on edges incident to v . The deficiency of α at vertex v ∈ V ( G ) , denoted by d e f ( v , α ) , is the minimum number of integers which must be added to S ( v , α ) to form an interval, and the deficiency d e f ( G , α ) of a proper edge-coloring α of G is defined as the sum ∑ v ∈ V ( G ) d e f ( v , α ) . The deficiency of a graph G , denoted by d e f ( G ) , is defined as follows: d e f ( G ) = min α d e f ( G , α ) , where minimum is taken over all possible proper edge-colorings of G . For a graph G , the smallest and the largest values of t for which it has a proper t -edge-coloring α with deficiency d e f ( G , α ) = d e f ( G ) are denoted by w d e f ( G ) and W d e f ( G ) , respectively. In this paper, we obtain some bounds on w d e f ( G ) and W d e f ( G ) . In particular, we show that for any l ∈ N , there exists a graph G such that d e f ( G ) > 0 and W d e f ( G ) − w d e f ( G ) ≥ l . It is known that for the complete graph K 2 n + 1 , d e f ( K 2 n + 1 ) = n ( n ∈ N ). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Haluszczak posed the following conjecture on the deficiency of near-complete graphs: if n ∈ N , then d e f ( K 2 n + 1 − e ) = n − 1 . In this paper, we confirm this conjecture.
- Published
- 2017
15. A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
- Author
-
Insung Ihm and Jung-Heum Park
- Subjects
Discrete mathematics ,Induced path ,Applied Mathematics ,Shortest-path tree ,0102 computer and information sciences ,02 engineering and technology ,Path cover ,01 natural sciences ,Hamiltonian path ,Edge cover ,020202 computer hardware & architecture ,Combinatorics ,symbols.namesake ,010201 computation theory & mathematics ,Covering graph ,Graph power ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,Discrete Mathematics and Combinatorics ,Path graph ,Algorithm ,Mathematics - Abstract
For a connected graph G=(V(G),E(G)) and two disjoint subsets of V(G)A={1,,k} and B={1,,k}, a paired (many-to-many) k-disjoint path cover of G joining A and B is a vertex-disjoint path cover {P1,,Pk} such that Pi is a path from i to i for 1ik. In the recent paper, Park and Ihm (2014) presented a necessary and sufficient condition for a paired 2-disjoint path cover joining two vertex sets to exist in the cube of a connected graph. In this paper, we propose an O(|V(G)|+|E(G)|)-time algorithm that actually finds such a paired 2-disjoint path cover. In particular, we show that, in order to build a desired disjoint path cover, it is sufficient to consider only the edges of a carefully selected spanning tree of the graph and at most one additional edge not in the tree, which allows an efficient linear-time algorithm.
- Published
- 2017
16. Counting independent sets in tree convex bipartite graphs
- Author
-
Min-Sheng Lin and Chien-Min Chen
- Subjects
Discrete mathematics ,Mathematics::Combinatorics ,Applied Mathematics ,010102 general mathematics ,Convex bipartite graph ,0102 computer and information sciences ,Tree-depth ,01 natural sciences ,Complete bipartite graph ,Combinatorics ,Computer Science::Discrete Mathematics ,010201 computation theory & mathematics ,Chordal graph ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Independent set ,Bipartite graph ,Discrete Mathematics and Combinatorics ,Cograph ,Maximal independent set ,0101 mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
The problems of counting independent sets, maximal independent sets, and independent perfect dominating sets are #P-complete for bipartite graphs, but can be solved in polynomial time for convex bipartite graphs, which are a subclass of bipartite graphs This paper studies these problems for tree convex bipartite graphs, which are a class of graphs between bipartite graphs and convex bipartite graphs. A bipartite graph G with bipartition (XY) is called tree convex, if a tree T defined on X exists, such that for every vertex y in Y, the neighbors of y form a subtree of T If the associated tree T is simply a path, then G is just a convex bipartite graph. This paper first proves that the problems of counting independent sets, maximal independent sets, and independent perfect dominating sets remain #P-complete for tree convex bipartite graphs even when the associated tree T is only a comb or a star. This paper then presents polynomial-time algorithms to solve these problems for tree convex bipartite graphs when the associated tree T is restricted to a triad, which consists of three paths with one common endpoint.
- Published
- 2017
17. On semidefinite least squares and minimal unsatisfiability
- Author
-
Manuel V. C. Vieira and Miguel F. Anjos
- Subjects
Discrete mathematics ,Semidefinite embedding ,Semidefinite programming ,Quadratically constrained quadratic program ,Optimization problem ,Applied Mathematics ,Mathematics::Optimization and Control ,0102 computer and information sciences ,02 engineering and technology ,Computer Science::Artificial Intelligence ,Computer Science::Computational Complexity ,01 natural sciences ,Satisfiability ,Combinatorics ,Propositional formula ,010201 computation theory & mathematics ,Computer Science::Logic in Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Conjunctive normal form ,Farkas' lemma ,Mathematics - Abstract
This paper provides new results on the application of semidefinite optimization to satisfiability by studying the connection between semidefinite optimization and minimal unsatisfiability. We use a semidefinite least squares problem to assign weights to the clauses of a propositional formula in conjunctive normal form. We then show that these weights are a measure of the necessity of each clause in rendering the formula unsatisfiable, the weight of a necessary clause is strictly greater than the weight of any unnecessary clause. In particular, we show the following results: first, if a formula is minimal unsatisfiable, then all of its clauses have the same weight; second, if a clause does not belong to any minimal unsatisfiable subformula, then its weight is zero. An additional contribution of this paper is a demonstration of how the infeasibility of a semidefinite optimization problem can be tested using a semidefinite least squares problem by extending an earlier result for linear optimization. The connection between the semidefinite least squares problem and Farkas’ Lemma for semidefinite optimization is also discussed.
- Published
- 2017
18. Hamming weights of symmetric Boolean functions
- Author
-
Thomas W. Cusick
- Subjects
Discrete mathematics ,Symmetric Boolean function ,Parity function ,Applied Mathematics ,Stanley symmetric function ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Combinatorics ,Symmetric function ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Elementary symmetric polynomial ,Boolean function ,Hamming weight ,Ring of symmetric functions ,Mathematics - Abstract
It has been known since 1996 (work of Cai et al.) that the sequence of Hamming weights { w t ( f n ( x 1 , ź , x n ) ) } , where f n is a symmetric Boolean function of degree d in n variables, satisfies a linear recurrence with integer coefficients. In 2011, Castro and Medina used this result to show that a 2008 conjecture of Cusick, Li and Stźnicź about when an elementary symmetric Boolean function can be balanced is true for all sufficiently large n . Quite a few papers have been written about this conjecture, but it is still not completely settled. Recently, Guo, Gao and Zhao proved that the conjecture is equivalent to the statement that all balanced elementary symmetric Boolean functions are trivially balanced. This motivates the further study of the weights of symmetric Boolean functions f n . In this paper we prove various new results on the trivially balanced functions. We also determine a period (sometimes the minimal one) for the sequence of weights w t ( f n ) modulo any odd prime p , where f n is any symmetric function, and we prove some related results about the balanced symmetric functions.
- Published
- 2016
19. On the fractional strong metric dimension of graphs
- Author
-
Cong X. Kang
- Subjects
Discrete mathematics ,Geodesic ,Applied Mathematics ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Upper and lower bounds ,Graph ,Metric dimension ,Combinatorics ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Mathematics - Abstract
For any two vertices x and y of a graph G , let S { x , y } denote the set of vertices z such that either x lies on a y - z geodesic or y lies on an x - z geodesic. For a function g defined on V ( G ) and U ź V ( G ) , let g ( U ) = ź x ź U g ( x ) . A function g : V ( G ) ź 0 , 1 is a strong resolving function of G if g ( S { x , y } ) ź 1 , for every pair of distinct vertices x , y of G . The fractional strong metric dimension, s d i m f ( G ) , of a graph G is min { g ( V ( G ) ) : g źisźaźstrongźresolvingźfunctionźofź G } . This paper furthers the study of fractional strong metric dimension initiated in COCOA 2013 (Lecture Notes in Comput. Sci.). First, we clarify or correct the proofs to two characterization theorems contained in two papers on fractional (strong) metric dimension. Next, results on fractional strong metric dimension analogous to the work of Feng, Lv, and Wang on fractional metric dimension are offered. We provide new upper and lower bounds on s d i m f ( G ) , partly in analogy with the work done by Feng et al. and partly by exploiting the particular nature of the strong metric dimension. Finally, motivated by the work of Arumugam, Mathew, and Shen, we describe a class of graphs G for which s d i m f ( G ) = | V ( G ) | 2 .
- Published
- 2016
20. Orientations of graphs with maximum Wiener index
- Author
-
Riste Škrekovski, Aleksandra Tepeh, and Martin Knor
- Subjects
Discrete mathematics ,Vertex (graph theory) ,Strongly connected component ,Applied Mathematics ,010102 general mathematics ,Digraph ,0102 computer and information sciences ,Directed graph ,Wiener index ,01 natural sciences ,Graph ,Combinatorics ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,0101 mathematics ,Mathematics - Abstract
In this paper we study the Wiener index (i.e.,źthe total distance or the transmission number) of not necessarily strongly connected digraphs. In order to do so, if in a digraph there is no directed path from a vertex a to a vertex b , we follow the convention that d ( a , b ) = 0 , which was independently introduced in several studies of directed networks. By extending the results of Plesnik and Moon we characterize tournaments with the maximal and the second maximal Wiener index. We also study oriented Theta-graphs and, as a consequence, we obtain that an orientation of a given graph which yields the maximum Wiener index is not necessarily strongly connected. In particular, we characterize orientations of Theta-graphs ź a , b , 0 and ź a , b , 1 which result in the maximum Wiener index. In addition, orientations with the maximum Wiener index among strongly connected orientations of ź a , b , c are characterized. We conclude the paper with several open problems.
- Published
- 2016
21. Game total domination for cycles and paths
- Author
-
Paul Dorbec and Michael A. Henning
- Subjects
Discrete mathematics ,Domination analysis ,Applied Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Graph ,Vertex (geometry) ,Combinatorics ,010201 computation theory & mathematics ,Dominator ,Dominating set ,Mod ,Discrete Mathematics and Combinatorics ,0101 mathematics ,Mathematics - Abstract
In this paper, we continue the study of the recently introduced total domination game in graphs. A vertex u in a graph G totally dominates a vertex? v if u is adjacent to v in G . A total dominating set of G is a set S of vertices of G such that every vertex of G is totally dominated by a vertex in S . The total domination game played on G consists of two players, named Dominator and Staller, who alternately take turns choosing vertices of G such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. Dominator's goal is to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game total domination number, γ tg ( G ) , of G is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, γ tg ' ( G ) , of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper we determine γ tg ( G ) and γ tg ' ( G ) when G is a cycle or a path. In particular, we show that for a cycle C n on n ? 3 vertices, γ tg ( C n ) = ? 2 n + 1 3 ? - 1 when n ? 4 ( mod 6 ) and γ tg ( C n ) = ? 2 n + 1 3 ? otherwise. Further, γ tg ' ( C n ) = ? 2 n 3 ? - 1 when n ? 2 ( mod 6 ) and γ tg ' ( C n ) = ? 2 n 3 ? otherwise. For a path P n on n ? 3 vertices, we show that γ tg ' ( P n ) = ? 2 n 3 ? . Further, γ tg ( P n ) = ? 2 n 3 ? when n ? 5 ( mod 6 ) and ? 2 n 3 ? otherwise.
- Published
- 2016
22. Weak saturation number for multiple copies of the complete graph with a star removed
- Author
-
Yajuan Cui and Liqun Pu
- Subjects
Discrete mathematics ,Applied Mathematics ,010102 general mathematics ,Complete graph ,A* search algorithm ,0102 computer and information sciences ,01 natural sciences ,Complete bipartite graph ,Graph ,law.invention ,Combinatorics ,010201 computation theory & mathematics ,law ,Discrete Mathematics and Combinatorics ,Graph toughness ,0101 mathematics ,Saturation (chemistry) ,Mathematics - Abstract
Let K t denote the complete graph with t vertices, and let K 1 , m (a star with m edges) denote the complete bipartite graph with partite sets of sizes 1 and m . A graph G of order n is weakly F -saturated if G contains no copy of F , and there is an ordering of the edges in E ( K n ? G ) so that if they are added one at a time, then each edge added creates a new copy of F . In this paper, the weak saturation number of multiple copies of K t - K 1 , m is determined for positive integers t and m ( 1 ? m < t - 1 ) . This completely answers the question 3 in paper Faudree et?al. (2013), partially answers the question 4 in paper Faudree et?al. (2013) and the question 1 in Faudree and Gould (2014).
- Published
- 2016
23. On the first-order edge tenacity of a graph
- Author
-
Amin Ghodousian, Dara Moazzami, and Bahareh Bafandeh
- Subjects
Discrete mathematics ,Strongly regular graph ,Applied Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Planar graph ,Combinatorics ,symbols.namesake ,010201 computation theory & mathematics ,Graph power ,Random regular graph ,symbols ,Graph minor ,Discrete Mathematics and Combinatorics ,Bound graph ,Graph toughness ,Graph factorization ,Mathematics - Abstract
The first-order edge-tenacity T 1 ( G ) of a graph G is defined as T 1 ( G ) = m i n { | X | + ? ( G - X ) ω ( G - X ) - 1 } where the minimum is taken over every edge-cutset X that separates G into ω ( G - X ) components, and by ? ( G - X ) we denote the order (the number of edges) of a largest component of G - X .The objective of this paper is to study this concept of edge-tenacity and determining this quantity for some special classes of graphs. We calculate the first-order edge-tenacity of a complete n -partite graph. We shall obtain the first-order edge-tenacity of maximal planar graphs, maximal outerplanar graphs, and k -trees. Let G be a graph of order p and size q , we shall call the least integer r , 1 ? r ? p - 1 , with T r ( G ) = q p - r the balancity of G and denote it by b ( G ) . Note that the balancity exists since T r ( G ) = q p - r if r = p - 1 . In general, it is difficult to determine the balancity of a graph. In this paper, we shall first determine the balancity of a special class of graphs and use this to find an upper bound for the balancity of an arbitrary graph.
- Published
- 2016
24. A family of efficient six-regular circulants representable as a Kronecker product
- Author
-
Pranava K. Jha
- Subjects
Kronecker product ,Discrete mathematics ,Applied Mathematics ,010102 general mathematics ,Torus ,Möbius ladder ,0102 computer and information sciences ,01 natural sciences ,Graph ,Combinatorics ,symbols.namesake ,010201 computation theory & mathematics ,symbols ,Discrete Mathematics and Combinatorics ,Embedding ,0101 mathematics ,Twist ,Circulant matrix ,Mathematics - Abstract
Broere and Hattingh proved that the Kronecker product of two circulants whose orders are co-prime is a circulant itself. This paper builds on this result to construct a family of efficient three-colorable, six-regular circulants representable as the Kronecker product of a Mobius ladder and an odd cycle. The order of each graph is equal to 4 d 2 - 2 d - 2 where d denotes the diameter and d ? 3 , 5 (mod 6). Additional results include (a) distance-wise vertex distribution of the circulant leading to its average distance that is about two-thirds of the diameter, (b) routing via shortest paths, and (c) an embedding of the circulant on a torus with a half twist. In terms of the order-diameter ratio and odd girth, the circulants in this paper surpass the well-known triple-loop networks having diameter d and order 3 d 2 + 3 d + 1 .
- Published
- 2016
25. Exact solutions for Latency-Bounded Target Set Selection Problem on some special families of graphs
- Author
-
Zishen Yang, Wei Wang, and Xianliang Liu
- Subjects
Discrete mathematics ,Rational number ,Applied Mathematics ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Upper and lower bounds ,Graph ,Vertex (geometry) ,Combinatorics ,010201 computation theory & mathematics ,Chordal graph ,Bounded function ,Independent set ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Maximal independent set ,Mathematics - Abstract
In the t -Latency-Bounded Target Set Selection ( t -LBTSS) problem, we are given a simple graph G = ( V , E ) , a certain latency bound t and a threshold function ? ( v ) = ? ? d ( v ) ? for every vertex v of G , where 0 < ? < 1 is a rational number and d ( v ) is the degree of v in V , the goal is to find a target set S with smallest cardinality such that all vertices in V are activated by S by a so called "diffusion process" within t rounds as follows: Initially, all vertices in the target set become activate. Then at each step i of the process, each vertex get activated if the number of active vertices in its neighbor after i - 1 exceeds its threshold.For general graphs, the t -LBTSS problem is not only NP-hard, it is also hard to be approximated by Chen's inapproachability results (Chen, 2009). In this paper, we are interested in finding an optimal target set for some special family of graphs. A simple, tight but nontrivial inequality was presented which gives the lower bound of the total sum of degrees in a feasible target set to t -LBTSS problem, in terms of the number of edges in the graph. Necessary and sufficient conditions for equality to hold have been established, based on which we are able to construct families of infinite number of graphs for which the optimal solution to t -LBTSS problem become obvious. In particular, we gave an exact formula for the optimal solution of a kind of toroidal mesh graphs, while it seems difficult to tell what the optimal solutions are for these graphs without using the equality given in the paper.
- Published
- 2016
26. Semi-transitive orientations and word-representable graphs
- Author
-
Magnús M. Halldórsson, Sergey Kitaev, and Artem V. Pyatkin
- Subjects
Symmetric graph ,Comparability graph ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,law.invention ,Combinatorics ,law ,Line graph ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,QA ,Forbidden graph characterization ,Mathematics ,Universal graph ,Block graph ,Discrete mathematics ,Applied Mathematics ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Vertex-transitive graph ,010201 computation theory & mathematics ,020201 artificial intelligence & image processing ,Combinatorics (math.CO) ,Computer Science::Formal Languages and Automata Theory ,Graph product ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
A graph $G=(V,E)$ is a \emph{word-representable graph} if there exists a word $W$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $W$ if and only if $(x,y)\in E$ for each $x\neq y$. In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a \emph{semi-transitive orientation} defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of $G$ is the minimum $k$ such that $G$ is a representable by a word, where each letter occurs $k$ times; such a $k$ exists for any word-representable graph. We show that the representation number of a word-representable graph on $n$ vertices is at most $2n$, while there exist graphs for which it is $n/2$., arXiv admin note: text overlap with arXiv:0810.0310
- Published
- 2016
27. An extension of the Motzkin–Straus theorem to non-uniform hypergraphs and its applications
- Author
-
Yuejian Peng, Cheng Zhao, Qingsong Tang, and Hao Peng
- Subjects
Discrete mathematics ,Hypergraph ,Mathematics::Combinatorics ,Fundamental theorem ,Applied Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Graph ,Combinatorics ,symbols.namesake ,Computer Science::Discrete Mathematics ,010201 computation theory & mathematics ,symbols ,Discrete Mathematics and Combinatorics ,0101 mathematics ,Partially ordered set ,Lagrangian ,Mathematics - Abstract
In 1965, Motzkin and Straus established a remarkable connection between the order of a maximum clique and the Lagrangian of a graph and provided a new proof of Turan's theorem using the connection. The connection of Lagrangians and Turan densities can be also used to prove the fundamental theorem of Erd?s-Stone-Simonovits on Turan densities of graphs. Very recently, the study of Turan densities of non-uniform hypergraphs has been motivated by extremal poset problems and suggested by Johnston and Lu. In this paper, we attempt to explore the applications of Lagrangian method in determining Turan densities of non-uniform hypergraphs. We first give a definition of the Lagrangian of a non-uniform hypergraph, then give an extension of the Motzkin-Straus theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Applying it, we give an extension of the Erd?s-Stone-Simonovits theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Our approach follows from the approach in Keevash's paper Keevash (2011).
- Published
- 2016
28. Directed elimination games
- Author
-
Sebastian Ordyniak, Viktor Engelmann, and Stephan Kreutzer
- Subjects
Discrete mathematics ,021103 operations research ,Applied Mathematics ,0211 other engineering and technologies ,Comparability graph ,0102 computer and information sciences ,02 engineering and technology ,Directed graph ,Directed acyclic graph ,Tree-depth ,01 natural sciences ,Feedback arc set ,Combinatorics ,010201 computation theory & mathematics ,Dominating set ,Discrete Mathematics and Combinatorics ,Graph (abstract data type) ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics ,Moral graph - Abstract
While tools from structural graph theory such as tree- or path-width have proved to be highly successful in coping with computational intractability on undirected graphs, corresponding width measures for directed graphs have not yet fulfilled their promise for broad algorithmic applications on directed graphs. One reason for this is that in most existing digraph width measures the class of acyclic digraphs has small width which immediately implies hardness of problems such as computing directed dominating sets.Fernau and Meister (2014) introduce the concept of elimination width and a corresponding graph searching game which overcomes this problem with acyclic digraphs. In their paper, the focus was on structural characterizations of classes of digraphs of bounded elimination width.In this paper we study elimination width from an algorithmic and graph searching perspective. We analyse variations of the elimination width game and show that this leads to width measures on which the directed dominating set problem and some variants of it become tractable.
- Published
- 2016
29. Factorization of network reliability with perfect nodes II: Connectivity matrix
- Author
-
Juan Manuel Burgos
- Subjects
Discrete mathematics ,Applied Mathematics ,020206 networking & telecommunications ,Graph theory ,Mathematics - Rings and Algebras ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Matrix (mathematics) ,Factorization ,Rings and Algebras (math.RA) ,010201 computation theory & mathematics ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Algebraic number ,Connectivity ,Mathematics - Abstract
We prove the determinant connectivity matrix formula. Mathematically, the proof introduces novel techniques based on an algebraic approach and connectivity properties. Although this is the second part of a previous paper and has its original motivation there, the paper is self contained and the result is interesting in itself.
- Published
- 2016
30. Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs
- Author
-
Emeric Gioan and Christophe Paul
- Subjects
Discrete mathematics ,Applied Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Split decomposition ,Distance hereditary graphs ,Fully dynamic algorithms ,Combinatorics ,Modular decomposition ,Indifference graph ,Pathwidth ,010201 computation theory & mathematics ,Chordal graph ,Permutation graph ,Discrete Mathematics and Combinatorics ,Cograph ,Maximal independent set ,Split graph ,0101 mathematics ,Algorithm ,Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give structural and incremental characterizations, leading to optimal fully dynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on the new combinatorial framework of graph-labelled trees used to represent the split decomposition of general graphs (and also the modular decomposition). The point of the paper is to use bijections between the aforementioned graph classes and graph-labelled trees whose nodes are labelled by cliques and stars. We mention that this bijective viewpoint yields directly an intersection model for the class of distance hereditary graphs.
- Published
- 2012
- Full Text
- View/download PDF
31. Complexity of (p,1)-total labelling
- Author
-
Frédéric Havet and Stéphan Thomassé
- Subjects
Discrete mathematics ,Vertex (graph theory) ,Applied Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Upper and lower bounds ,Graph ,Combinatorics ,010201 computation theory & mathematics ,Labelling ,Bipartite graph ,Discrete Mathematics and Combinatorics ,Cubic graph ,Regular graph ,0101 mathematics ,Graph labelling ,Mathematics - Abstract
A (p,1)-total labelling of a graph G=(V,E) is a total colouring L from V@?E into {0,...,l} such that |L(v)-L(e)|>=p whenever an edge e is incident to a vertex v. The minimum l for which G admits a (p,1)-total labelling is denoted by @l"p(G). The case p=1 corresponds to the usual notion of total colouring, which is NP-hard to compute even for cubic bipartite graphs [C.J. McDiarmid, A. Sanchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994), 155-162]. In this paper we assume p>=2. It is easy to show that @l"p(G)>=@D+p-1, where @D is the maximum degree of G. Moreover, when G is bipartite, @D+p is an upper bound for @l"p(G), leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether @l"p(G) is equal to @D+p-1 or to @D+p when G is bipartite. This is trivial when @D@?p, polynomial when @D=3 and p=2, and NP-complete in the remaining cases.
- Published
- 2009
32. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
- Author
-
Khaled Elbassioni, Endre Boros, Leonid Khachiyan, and Vladimir Gurvich
- Subjects
Dualization ,Hypergraph ,Empty boxes ,0102 computer and information sciences ,02 engineering and technology ,Quasi-polynomial ,01 natural sciences ,Combinatorics ,Reduction (complexity) ,Transversal (geometry) ,Frequent sets ,Integer ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Boolean function ,Mathematics ,Discrete mathematics ,Applied Mathematics ,Monotone properties ,Hypergraph transversals ,Monotone polygon ,010201 computation theory & mathematics ,Bounded function ,020201 artificial intelligence & image processing ,Generation algorithms ,Algorithm - Abstract
Given a finite set V, and a hypergraph H⊆2V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618–628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50–63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.
- Published
- 2006
33. The 3-extra conditional diagnosability of balanced hypercubes under MM∗ model
- Author
-
Qiang Zhu, Yiguang Bai, Lili Li, and Xing Zhang
- Subjects
Discrete mathematics ,Interconnection ,Applied Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Measure (mathematics) ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Hypercube ,Reliability (statistics) ,Mathematics - Abstract
Diagnosis plays an important role in measuring the reliability of an interconnection network, and the diagnosability of interconnection networks has been widely investigated. For a system G , Zhang et al. introduced h -extra conditional diagnosability, denoted by t h ( G ) , which is a novel measure of diagnosability. In this paper, several new structural properties of balanced hypercubes have been derived. Based on these properties, the 3-extra conditional diagnosability of an n -dimensional balanced hypercube is determined to be t 3 ( B H n ) = 4 n − 1 for n ≥ 5 under the MM ∗ model.
- Published
- 2022
34. New upper and lower bounds on the channel capacity of read/write isolated memory
- Author
-
Xuerong Yong, Mordecai J. Golin, Yuanping Zhang, and Li Sheng
- Subjects
Two-dimensional codes ,Computer science ,Eigenvalue ,Binary number ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Upper and lower bounds ,Combinatorics ,Matrix (mathematics) ,Channel capacity ,0202 electrical engineering, electronic engineering, information engineering ,Symmetric matrix ,Discrete Mathematics and Combinatorics ,Logical matrix ,Eigenvalues and eigenvectors ,Computer Science::Information Theory ,Mathematics ,Discrete mathematics ,Capacity ,Applied Mathematics ,020206 networking & telecommunications ,Channel graph ,010201 computation theory & mathematics ,Symbol (programming) ,Runlength-limited codes ,Rewriting ,Constrained arrays ,Algorithm ,Communication channel - Abstract
In this paper, we refine upper and lower bounds for the channel capacity of a serial, binary rewritable medium in which no consecutive locations may store 1's and no consecutive locations may be altered during a single rewriting pass. This problem was originally examined by Cohn (Discrete. Appl. Math. 56 (1995) 1) who proved that C, the channel capacity of the memory, in bits per symbol per rewrite, satisfies 0.50913 ... ≤ C ≤ 0.56029 ... In this paper, we show how to model the problem as a constrained two-dimensional binary matrix problem and then modify recent techniques for dealing with such matrices to derive improved bounds of 0.53500... ≤ C ≤ 0.55209... .
- Published
- 2004
35. A faster FPTAS for counting two-rowed contingency tables
- Author
-
Tzvi Alon and Nir Halman
- Subjects
Contingency table ,Discrete mathematics ,Scheme (programming language) ,Applied Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Polynomial-time approximation scheme ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,computer ,Mathematics ,computer.programming_language - Abstract
In this paper we provide a deterministic fully polynomial time approximation scheme (FPTAS) for counting two-rowed contingency tables that is faster than any either deterministic or randomized approximation scheme for this problem known to date. Our FPTAS is derived via a somewhat sophisticated usage of the method of K -approximation sets and functions introduced by Halman et al. (2009).
- Published
- 2021
36. The pagenumber of k-trees is O(k)
- Author
-
Joseph L. Ganley and Lenwood S. Heath
- Subjects
Discrete mathematics ,Book embedding ,Graph labeling ,k-trees ,Graph embedding ,Pagenumber ,Treewidth ,Applied Mathematics ,0102 computer and information sciences ,02 engineering and technology ,Strength of a graph ,01 natural sciences ,Combinatorics ,010201 computation theory & mathematics ,Graph power ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Graph toughness ,Complement graph ,MathematicsofComputing_DISCRETEMATHEMATICS ,Toroidal graph ,Mathematics - Abstract
A k-tree is a graph defined inductively in the following way: the complete graph Kk is a k-tree, and if G is a k-tree, then the graph resulting from adding a new vertex adjacent to k vertices inducing a Kk in G is also a k-tree. This paper examines the book-embedding problem for k-trees. A book embedding of a graph maps the vertices onto a line along the spine of the book and assigns the edges to pages of the book such that no two edges on the same page cross. The pagenumber of a graph is the minimum number of pages in a valid book embedding. In this paper, it is proven that the pagenumber of a k-tree is at most k+1. Furthermore, it is shown that there exist k-trees that require k pages. The upper bound leads to bounds on the pagenumber of a variety of classes of graphs for which no bounds were previously known.
- Published
- 2001
- Full Text
- View/download PDF
37. Stabbing information of a simple polygon
- Author
-
Ferran Hurtado, Hazel Everett, Marc Noy, Models, algorithms and geometry for computer graphics and vision (ISA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), and Universitat Politècnica de Catalunya [Barcelona] (UPC)
- Subjects
Convex hull ,[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] ,Structure (category theory) ,0102 computer and information sciences ,02 engineering and technology ,Computer Science::Computational Geometry ,order type ,01 natural sciences ,Combinatorics ,Set (abstract data type) ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Simple polygon ,Mathematics ,Discrete mathematics ,stabbing information ,Applied Mathematics ,Visibility (geometry) ,Object (computer science) ,visibility graphs ,Vertex (geometry) ,010201 computation theory & mathematics ,Order type ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Article dans revue scientifique avec comité de lecture.; The purpose of this paper is to investigate a new combinatorial object describing the structure of a simple polygon and compare it to other well-known objects such as the internal and external visibility graphs, the convex hull and the order type of the vertex set. We call the new object the stabbing information. In fact, we define three variations of the stabbing information, strong, weak and labelled, and explore the relationships among them. The main result of the paper is that strong stabbing information is sufficient to recover the convex hull, the internal and external visibility graphs and to determine which vertices are reflex and it is not sufficient to recover the order type of the vertex set. We also show that the labelled stabbing information is equivalent to the order type. We give algorithms for computing each of these new structures.
- Published
- 1999
38. Game edge-connectivity of graphs
- Author
-
Naoki Matsumoto and Tomoki Nakamigawa
- Subjects
Discrete mathematics ,Computer Science::Computer Science and Game Theory ,Spanning tree ,Applied Mathematics ,media_common.quotation_subject ,ComputingMilieux_PERSONALCOMPUTING ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,Characterization (mathematics) ,Infinity ,01 natural sciences ,Graph ,Corollary ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Cubic graph ,Enhanced Data Rates for GSM Evolution ,Invariant (mathematics) ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics ,media_common - Abstract
Recently, the authors introduced a game invariant of graphs, called a game connectivity. In this paper, we investigate the edge version of the invariant, called a game edge-connectivity, by introducing a new combinatorial game on a graph, called a graph edge-cutting game. The game is one of generalizations of a classical combinatorial game, named the Shannon switching game. As an analog of the study of the Shannon switching game, we have a complete characterization of graphs with game edge-connectivity infinity in terms of the number of edge-disjoint spanning trees. As a corollary of the above, any graph with edge-connectivity at least 4 has game edge-connectivity infinity. Thus, since determining the game edge-connectivity of a given cubic graph is the most interesting problem, we give a useful tool to estimate the game edge-connectivity of cubic graphs. Other than those above, we study many fundamental topics of the game edge-connectivity of graphs, and propose several open problems.
- Published
- 2021
39. The lower bound of the weightwise nonlinearity profile of a class of weightwise perfectly balanced functions
- Author
-
Sihong Su
- Subjects
Discrete mathematics ,Applied Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,Algebraic normal form ,01 natural sciences ,Upper and lower bounds ,010201 computation theory & mathematics ,Hadamard transform ,Discrete Mathematics and Combinatorics ,Hamming weight ,Constant (mathematics) ,Boolean function ,Stream cipher ,Integer (computer science) ,Mathematics - Abstract
Boolean functions satisfying good cryptographic criteria when restricted to the set of vectors with constant Hamming weight play an important role in the recent FLIP stream cipher. Although the nonlinearity of Boolean functions can be calculated rapidly by Walsh transform, the nonlinearity of the Boolean functions with restricted input seems to be very difficult to calculate. In this paper, a class of weightwise perfectly balanced Boolean functions with very simple algebraic normal form is proposed. Then, the cryptographic properties of the weightwise perfectly balanced Boolean functions are discussed. Especially, the lower bound of the weightwise nonlinearity of these 2 m -variable functions is given for any positive integer m .
- Published
- 2021
40. A local analysis to determine all optimal solutions of p-k-max location problems on networks
- Author
-
Michael Stiglmayr, Kathrin Klamroth, Justo Puerto, and Teresa Schnepper
- Subjects
Discrete mathematics ,Polynomial ,Generalization ,Applied Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,01 natural sciences ,Set (abstract data type) ,Local analysis ,010201 computation theory & mathematics ,Dominating set ,Outlier ,Discrete Mathematics and Combinatorics ,Graph (abstract data type) ,Mathematics - Abstract
As a generalization of p -center location problems, p - k - max problems minimize the k th largest weighted distance to the customers. In this way, outlier facilities can be detected automatically and excluded from consideration when locating new facilities. Similar to p -center problems, p - k - max problems often have many alternative optimal solutions. Knowledge of the complete optimal set allows to select a most preferred solution using secondary criteria. In this paper, a general solution method is suggested that guarantees to find all alternative optimal solutions of p - k - max problems on networks. This is realized by performing a local analysis on the edges of the underlying graph and identifying edge segments on which the p - k - max function is linear. It is shown that the complete optimal set can be represented by an extended finite dominating set (FDS) which is of polynomial size for fixed values of p . Numerical tests indicate that computing the set of optimal solutions compared to the computation of a single optimal solution of a p - k - max problem requires on average less than 15% additional computing effort. This computational efficiency allows one to select the most preferred solution among them using secondary objectives, like backup coverage or the Weber function.
- Published
- 2021
41. The complexity of recognizing minimally tough graphs
- Author
-
Gyula Y. Katona, Kitti Varga, and István Kovács
- Subjects
FOS: Computer and information sciences ,Vertex (graph theory) ,Discrete Mathematics (cs.DM) ,Computer Science::Neural and Evolutionary Computation ,0211 other engineering and technologies ,G.2.2 ,Hardware_PERFORMANCEANDRELIABILITY ,0102 computer and information sciences ,02 engineering and technology ,Edge (geometry) ,01 natural sciences ,GeneralLiterature_MISCELLANEOUS ,Set (abstract data type) ,FOS: Mathematics ,Complexity class ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Computer Science::Databases ,G.2.2, F.1.3 ,Computer Science::Cryptography and Security ,Mathematics ,Discrete mathematics ,Quantitative Biology::Biomolecules ,Quantitative Biology::Neurons and Cognition ,Intersection (set theory) ,Applied Mathematics ,021107 urban & regional planning ,F.1.3 ,Graph ,010201 computation theory & mathematics ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
A graph is called t -tough if the removal of any vertex set S that disconnects the graph leaves at most | S | ∕ t components. The toughness of a graph is the largest t for which the graph is t -tough. A graph is minimally t -tough if the toughness of the graph is t and the deletion of any edge from the graph decreases the toughness. The complexity class DP is the set of all languages that can be expressed as the intersection of a language in NP and a language in coNP. In this paper, we prove that recognizing minimally t -tough graphs is DP-complete for any positive rational number t . We introduce a new notion called weighted toughness, which has a key role in our proof.
- Published
- 2021
42. Polyhedral results for the precedence-constrained knapsack problem
- Author
-
E. Andrew Boyd
- Subjects
Convex hull ,Discrete mathematics ,021103 operations research ,Applied Mathematics ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Combinatorics ,Polyhedron ,Cover (topology) ,010201 computation theory & mathematics ,Knapsack problem ,Combinatorial optimization ,Discrete Mathematics and Combinatorics ,Integer programming ,Constraint (mathematics) ,Integer (computer science) ,Mathematics - Abstract
A problem characteristic common to a number of important integer programming problems is that of precedence constraints: a transitive collection of constraints of the form xj ≤ xi with 0 ≤ xi ≤ 1, 0 ≤ xj ≤ 1, xi, xj integer. Precedence constraints are of interest both because they arise frequently in integer programming applications and because the convex hull of feasible integer points is the same as the region obtained by relaxing the integrality restrictions. This paper investigates the polyhedral structure of the convex hull of feasible integer points when the precedence constraints are complicated by an additional constraint or, more generally, by additional constraints defining an independence system. Sequential lifting for independence systems with precedence constraints is discussed and extensions of the cover and 1-configuration inequalities known for the knapsack polytope are presented. A general procedure for inducing facets called rooting is introduced and a variety of facets based on rooting are developed. The paper concludes by discussing a procedure for coalescing constraints related to minimal covers into facets.
- Published
- 1993
- Full Text
- View/download PDF
43. On polynomial solvability of the high multiplicity total weighted tardiness problem
- Author
-
Frieda Granot and Jadranka Skorin-Kapov
- Subjects
Discrete mathematics ,021103 operations research ,Job shop scheduling ,Tardiness ,Applied Mathematics ,0211 other engineering and technologies ,Multiplicity (mathematics) ,0102 computer and information sciences ,02 engineering and technology ,Transportation theory ,01 natural sciences ,Weighting ,Combinatorics ,Quadratic equation ,010201 computation theory & mathematics ,Bounded function ,Discrete Mathematics and Combinatorics ,Time complexity ,Mathematics - Abstract
In a recent paper Hochbaum developed a polynomial algorithm for solving a scheduling problem of minimizing the total weighted tardiness for a large number of unit length jobs which can be partitioned into few sets of jobs with identical due dates and penalty weights. The number of unit jobs in a set is called the multiplicity of that set. The problem was formulated in Hochbaum as an integer quadratic nonseparable transportation problem and solved, in polynomial time, independent of the size of the multiplicities and the due dates but depending on the penalty weights. In this paper we show how to solve the above problem in polynomial time which is independent of the sizes of the weights. The running time of the algorithm depends on the dimension of the problem and only the size of the maximal difference between two consecutive due dates. In the case where the due dates are large, but the size of the maximal difference between two consecutive due dates is polynomially bounded by the dimension of the problem, the algorithm runs in strongly polynomial time.
- Published
- 1993
- Full Text
- View/download PDF
44. Zombie number of the Cartesian product of graphs
- Author
-
Ali Keramatipour and Behnam Bahrak
- Subjects
Discrete mathematics ,Conjecture ,Cartesian product of graphs ,Computational complexity theory ,Applied Mathematics ,Zombie ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,Cartesian product ,01 natural sciences ,Graph ,symbols.namesake ,010201 computation theory & mathematics ,symbols ,Discrete Mathematics and Combinatorics ,Connectivity ,Mathematics - Abstract
Zombies and Survivor is a variant of the pursuit–evasion game Cops and Robber(s), with the difference that zombies must always move closer to the survivor. The game is played on a simple connected graph by two players. The goal of the zombies is to catch the survivor while the survivor’s objective is to avoid being captured. The zombie number of G , denoted as , is the minimum number of zombies required to capture a single survivor on G , no matter what moves the survivor make. In this paper, we prove a conjecture by Fitzpatrick et al. (2016) about the zombie number of the Cartesian product of two graphs. This result provides a new proof for . We also introduce a new problem regarding capture time in the Cartesian product of two graphs. At last, we study computational complexity of finding the zombie number of a graph G , with and without a limited capture time.
- Published
- 2021
45. Reliability measure of multiprocessor system based on enhanced hypercubes
- Author
-
Jiafei Liu, Shuming Zhou, Liqiong Xu, and Shanshan Yin
- Subjects
Discrete mathematics ,010201 computation theory & mathematics ,Applied Mathematics ,0211 other engineering and technologies ,Discrete Mathematics and Combinatorics ,Network structure ,021107 urban & regional planning ,Multiprocessing ,0102 computer and information sciences ,02 engineering and technology ,Hypercube ,01 natural sciences ,Mathematics - Abstract
Reliability measure of multiprocessor systems is of significant importance to the design and maintenance of multiprocessor systems. Based on edge connectivity, more refined quantitative indicators for the reliability of multiprocessor systems have been introduced. The extra edge connectivity and the component edge connectivity, as two important parameters to evaluate the robustness of multiprocessor systems, are explored extensively. In this paper, we first determine the h -extra edge connectivity of the enhanced hypercube Q n , k (one potential alternative of hypercube) for 1 ≤ h ≤ 2 ⌈ n 2 ⌉ + 1 , n ≥ 2 k + 4 and 1 ≤ h ≤ 2 ⌈ n 2 ⌉ , n ≤ 2 k + 3 , k ≥ 3 . Some previous results in Zhang et al. (2016) and Sabir et al. (2019) are extended. Moreover, we also establish the g -component edge connectivity of the n -dimensional enhanced hypercube Q n , k for 1 ≤ g ≤ 2 ⌈ n 2 ⌉ + 1 , n ≥ 13 . As an easy extension, similar results for folded hypercube F Q n , another popular network structure, are readily derived.
- Published
- 2021
46. Representations of bicircular matroids
- Author
-
Collette R. Coullard, John G. del Greco, and Donald K. Wagner
- Subjects
Discrete mathematics ,Applied Mathematics ,010102 general mathematics ,Weighted matroid ,Incidence matrix ,0102 computer and information sciences ,Bicircular matroid ,01 natural sciences ,Matroid ,Combinatorics ,Graphic matroid ,Oriented matroid ,010201 computation theory & mathematics ,k-edge-connected graph ,Discrete Mathematics and Combinatorics ,Matroid partitioning ,0101 mathematics ,Mathematics - Abstract
A bicircular matroid is a matroid defined on the edge set of a graph. Two different graphs can have the same bicircular matroid. The first result of this paper is a characterization of the collection of graphs having the same bicircular matroid as a given arbitrary graph. A bicircular matroid can be represented by a matrix over the real numbers that has at most two nonzeros per column. Such a matrix can be viewed as an incidence matrix of a graph. The second result of this paper is that given almost any (in a sense to be made precise) collection of graphs G1,…,Gt having the same bicircular matroid M, there exist row-equivalent matrices N1,…,Nt each representing M, such that Ni is an incidence matrix of Gi for 1 ≤ i ≤ t. These results form the basis for an algorithm (presented in a subsequent paper) that under certain conditions converts a given linear-programming problem to a generalized-network flow problem.
- Published
- 1991
- Full Text
- View/download PDF
47. On colouring point visibility graphs
- Author
-
Bodhayan Roy and Ajit A. Diwan
- Subjects
Discrete mathematics ,Applied Mathematics ,Visibility graph ,Visibility (geometry) ,Point set ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Point (geometry) ,Chromatic scale ,Time complexity ,Clique number ,Mathematics - Abstract
In this paper we show that it can be decided in polynomial time whether or not the visibility graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be constructed in polynomial time. We show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4.
- Published
- 2020
48. The Hamming distances of repeated-root cyclic codes of length 5ps
- Author
-
Qin Yue and Xia Li
- Subjects
Discrete mathematics ,Applied Mathematics ,0211 other engineering and technologies ,Root (chord) ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,Coding theory ,Communications system ,01 natural sciences ,Prime (order theory) ,symbols.namesake ,Pauli exclusion principle ,010201 computation theory & mathematics ,symbols ,Discrete Mathematics and Combinatorics ,Hamming code ,Quantum ,BCH code ,Mathematics - Abstract
Due to the wide applications in consumer electronics, data storage systems and communication systems, cyclic codes have been an interesting research topic in coding theory. In this paper, let p be a prime with p ≥ 7 . We determine the Hamming distances of all repeated-root cyclic codes of length 5 p s over F q , where q = p m and both s and m are positive integers. Furthermore, we find all MDS cyclic codes of length 5 p s and take quantum synchronizable codes from repeated-root cyclic codes of length 5 p s . By comparing the minimum distances of 5 p s -length repeated-root cyclic codes to BCH codes of close lengths, we illustrated that quantum synchronizable codes constructed from repeated-root cyclic codes have in general better performance in correcting Pauli errors than those from BCH codes.
- Published
- 2020
49. Group parking permit problems
- Author
-
Mário César San Felice, Orlando Lee, and Murilo Santos de Lima
- Subjects
Discrete mathematics ,Matching (graph theory) ,Applied Mathematics ,0211 other engineering and technologies ,Approximation algorithm ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Reduction (complexity) ,Integer ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Interval (graph theory) ,Online algorithm ,Constant (mathematics) ,Time complexity ,Mathematics - Abstract
In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS’05), in which we are given a demand r t ∈ { 0 , 1 } for instant of time t = 0 , … , T − 1 , along with K permit types with lengths of time δ 1 , … , δ K and sub-additive costs. A permit is a pair ( k , t ˆ ) ∈ [ K ] × Z + , and it covers interval [ t ˆ , t ˆ + δ k ) . We wish to find a minimum-cost set of permits that covers every t with r t = 1 . Meyerson gave deterministic O ( K ) -competitive and randomized O ( lg K ) -competitive online algorithms for this problem, as well as matching lower bounds. The first variant we propose is the multi parking permit problem, in which an arbitrary demand is given at each instant ( r t ∈ Z + ) and we may buy multiple permits to serve it. We prove that the offline version of this problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields a deterministic O ( K ) -competitive online algorithm and a randomized O ( lg K ) -competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O ( lg n ) -approximation algorithm and a O ( lg K lg | V | ) -competitive online algorithm, where n is the number of requests and | V | is the size of the input metric. The second variant we propose is the group parking permit problem, in which we also have an arbitrary demand for each instant, and each permit of type k can be either a single permit, costing γ k and covering one demand per instant of time, or a group permit, which costs M ⋅ γ k for some constant M ≥ 1 and covers an arbitrary number of demands in the interval covered by this permit. (I.e., group permits have infinite capacity.) For this version of the problem, we give an 8-approximation algorithm and a deterministic O ( K ) -competitive online algorithm. The first result yields an improvement on the previous best approximation algorithm for the leasing version of the rent-or-buy problem. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid (2015), in which a permit type is defined by a length of time and an integer capacity. They presented a constant approximation algorithm and a deterministic O ( K ) -competitive online algorithm for a hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time algorithms. Moreover, these results yield approximation and competitive online algorithms for a hierarchical leasing version of the buy-at-bulk network design problem. We also show that their original pseudo-polynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NP-hard.
- Published
- 2020
50. Wirelength of embedding complete multipartite graphs into certain graphs
- Author
-
T. M. Rajalaxmi, G. Sethuraman, Jia-Bao Liu, and R. Sundara Rajan
- Subjects
Discrete mathematics ,Interconnection ,Graph embedding ,Applied Mathematics ,0211 other engineering and technologies ,Parallel algorithm ,021107 urban & regional planning ,Torus ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Multipartite ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Embedding ,Circulant matrix ,Mathematics ,Hyperbolic tree - Abstract
Graph embedding is an important technique that maps a guest graph into a host graph, usually an interconnection network. Many applications can be modeled as graph embedding. In architecture simulation, graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. The quality of an embedding can be measured by certain cost criteria. One of these criteria is the wirelength and has been well studied by many authors (Lai and Tsai, 2010 [ 18 ]; Fan and Jia, 2007 [ 10 ]; Han et al., 2010 [ 15 ]; Fang and Lai, 2005 [ 11 ]; Park and Chwa, 2000 [ 23 ]; Rajasingh et al., 2004; Yang et al., 2010; Yang, 2009 [ 27 ]; Manuel et al., 2009; Bezrukov et al., 1998; Rostami and Habibi, 2008 [ 26 ]; Choudum and Nahdini, 2004 [ 7 ]; Guu, 1997 [ 14 ]). In this paper, we compute the exact wirelength of embedding complete multipartite graphs into certain graphs, such as path, cycle, wheel, hypertree, cylinder, torus and 3-regular circulant graphs.
- Published
- 2020
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.