HKU Scholars Hubhttp://hub.hku.hkThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Sat, 21 May 2022 23:15:13 GMT2022-05-21T23:15:13Z50741- The Maximum-Weight Stable Matching Problem: Duality and Efficiencyhttp://hdl.handle.net/10722/241485Title: The Maximum-Weight Stable Matching Problem: Duality and Efficiency
Authors: Zang, W
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/10722/2414852011-01-01T00:00:00Z
- The Maximum-Weight Stable Matching Problem: Duality and Efficiencyhttp://hdl.handle.net/10722/241484Title: The Maximum-Weight Stable Matching Problem: Duality and Efficiency
Authors: Zang, W
Abstract: Given a preference system (G,≺) and an integral weight function de ned on the edge set of G (not
necessarily bipartite), the maximum-weight stable matching problem is to nd a stable matching of (G, ≺ )
with maximum total weight. We study this NP-hard problem using linear programming and polyhedral
approaches, and show that the Rothblum system for de ning the fractional stable matching polytope of
(G, ≺ ) is totally dual integral if and only if this polytope is integral if and only if (G, ≺ ) contains no so-
called semistable partitions with odd cycles. We also present a combinatorial polynomial-time algorithm
for the maximum-weight stable matching problem and its dual on any preference system containing no semistable partitions with odd cycles. (Joint work with X. Chen, G. Ding, and X. Hu.)
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/10722/2414842011-01-01T00:00:00Z
- A Polyhedral Description of Kernels http://hdl.handle.net/10722/239712Title: A Polyhedral Description of Kernels
Authors: Zang, W
Abstract: Let G be a digraph and let π(G) be the linear system consisting of nonnegativity, stability, and domination inequalities. We call G kernel ideal (resp. kernel Mengerian) if π(H) defines an integral polytope (resp. π(H) is totally dual integral) for each induced subgraph H of G. The purpose of this talk is to show that G is kernel ideal iff it is kernel Mengerian iff it contains none of three forbidden structures. (Joint work with Qin Chen and Xujin Chen)
Description: MS30 Graph Theory - Part II of III
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/10722/2397122016-01-01T00:00:00Z
- Packing circuits in matroidshttp://hdl.handle.net/10722/58957Title: Packing circuits in matroids
Authors: Ding, G; Zang, W
Abstract: The purpose of this paper is to characterize all matroids M that satisfy the following minimax relation: for any nonnegative integral weight function w defined on E(M), Maximum { k: M has k circuits ,(repetition, allowed) such that each element e of M is used at most 2w(e) times by these circuits = Minimum { ∑x ∈ X w(x): X is a collection of elements (repetition allowed) of M such that every circuit in M meets X at least twice}. Our characterization contains a complete solution to a research problem on 2-edge-connected subgraph polyhedra posed by Cornuéjols, Fonlupt, and Naddef in 1985, which was independently solved by Vandenbussche and Nemhauser in Vandenbussche and Nemhauser (J. Comb. Optim. 9:357-379, 2005). © 2008 Springer-Verlag.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10722/589572009-01-01T00:00:00Z
- A min-max theorem on tournamentshttp://hdl.handle.net/10722/75153Title: A min-max theorem on tournaments
Authors: Chen, X; Hu, X; Zang, W
Abstract: We present a structural characterization of all tournaments T = (V, A) such that, for any nonnegative integral weight function defined on V, the maximum size of a feedback vertex set packing is equal to the minimum weight of a triangle in T. We also answer a question of Frank by showing that it is N P-complete to decide whether the vertex set of a given tournament can be partitioned into two feedback vertex sets. In addition, we give exact and approximation algorithms for the feedback vertex set packing problem on tournaments. ©2007 Society for Industrial and Applied Mathematics.
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/10722/751532007-01-01T00:00:00Z
- Hamilton paths in toroidal graphshttp://hdl.handle.net/10722/156133Title: Hamilton paths in toroidal graphs
Authors: Thomas, R; Yu, X; Zang, W
Abstract: Tutte has shown that every 4-connected planar graph contains a Hamilton cycle. Grünbaum and Nash-Williams independently conjectured that the same is true for toroidal graphs. In this paper, we prove that every 4-connected toroidal graph contains a Hamilton path. © 2005 Elsevier Inc. All rights reserved.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10722/1561332005-01-01T00:00:00Z
- Recent Advances in Polyhedral Combinatoricshttp://hdl.handle.net/10722/252387Title: Recent Advances in Polyhedral Combinatorics
Authors: Zang, W
Description: Principal speaker
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10722/2523872017-01-01T00:00:00Z
- Recent Advances in Polyhedral Combinatoricshttp://hdl.handle.net/10722/252390Title: Recent Advances in Polyhedral Combinatorics
Authors: Zang, W
Abstract: Combinatorial optimization searches for an optimal object in a nite collection; typically the collection has a concise representation while the number of objects is huge. Polyhedral and linear programming techniques have proved to be very powerful and successful in tackling various combinatorial optimization problems, and the end products of these methods are often integral polyhedra or min-max relations. This area of combinatorial optimization is called polyhedral combinatorics. In this talk I shall give a brief survey of our recent results on polyhedral combinatorics, including a tournament ranking with no errors, a polyhedral description of kernels, and a characterization of the box-totally dual integral (box-TDI) matching polytope.
Description: Organizers: Society of Graph Theory and Combinatorics, ORSC ; Center of Graph Theory, Combinatorics & Network of AMSS ; Yuncheng University; Plenary talk
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10722/2523902017-01-01T00:00:00Z
- Recent Advances in Polyhedral Combinatoricshttp://hdl.handle.net/10722/252389Title: Recent Advances in Polyhedral Combinatorics
Authors: Zang, W
Abstract: Combinatorial optimization searches for an optimal object in a finite collection; typically the collection has a concise representation while the number of objects is huge. Polyhedral and linear programming techniques have proved to be very powerful and successful in tackling various combinatorial optimization problems, and the end products of these methods are often integral polyhedra or min-max relations. This area of combinatorial optimization is called polyhedral combinatorics. In this talk I shall give a brief survey of our recent results on polyhedral combinatorics, including a tournament ranking with no errors, a polyhedral description of kernels, and a characterization of the box-totally dual integral (box-TDI) matching polytope.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10722/2523892017-01-01T00:00:00Z
- Ramsey numbers involving large dense graphs and bipartite Turán numbershttp://hdl.handle.net/10722/156090Title: Ramsey numbers involving large dense graphs and bipartite Turán numbers
Authors: Li, Y; Zang, W
Abstract: We prove that for any fixed integer m ≥ 3 and constants δ > 0 and α ≥ 0, if F is a graph on m vertices and G is a graph on n vertices that contains at least (δ - o(1))n2/(log n)α edges as n → ∞, then there exists a constant c = c(m, δ) > 0 such that r(F, G) ≥ (c - o(1)) (n/(log n)α+1)(e(F)-1)/(m-2) where e(F) is the number of edges F. We also show that for any fixed k ≥ m ≥ 2, r(Km,k,Kn) ≤ (k - 1 + o(1)) (n/log n)m as n → ∞. In addition, we establish the following result: For an m × k bipartite graph F with minimum degree s and for any E > 0, if k > m/E then ex(F;N) ≥ N2-1/s-e for all sufficiently large N. This partially proves a conjecture of Erdos and Simonovits. © 2002 Elsevier Science (USA). All rights reserved.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/10722/1560902003-01-01T00:00:00Z
- TDI system and its application to approximation algorithmshttp://hdl.handle.net/10722/158854Title: TDI system and its application to approximation algorithms
Authors: Cai, Maocheng; Deng, Xiaotie; Zang, Wenan
Abstract: We obtain a necessary and sufficient condition for tournaments to possess a min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem in this class of tournaments; the condition and the algorithms are all based on a totally dual integral (TDI) system, a theoretical framework introduced by Edmonds and Giles for establishing min-max results. As a consequence, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.
Thu, 01 Jan 1998 00:00:00 GMThttp://hdl.handle.net/10722/1588541998-01-01T00:00:00Z
- Approximating the longest cycle problem on graphs with bounded degreehttp://hdl.handle.net/10722/158860Title: Approximating the longest cycle problem on graphs with bounded degree
Authors: Chen, G; Gao, Z; Yu, X; Zang, W
Abstract: In 1993, Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degree d ≥ 4 then G contains a cycle of length Ω(n logd-12), and showed that this bound is best possible if true. In this paper we present an O(n 3) algorithm for finding a cycle of length Ω(n logb2) in G, where b = max{64, 4d + 1}. Our result substantially improves the best existing bound Ω(n log2(d-1)2+12). © Springer-Verlag Berlin Heidelberg 2005.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10722/1588602005-01-01T00:00:00Z
- Approximate min-max relations on plane graphshttp://hdl.handle.net/10722/147122Title: Approximate min-max relations on plane graphs
Authors: Ma, J; Yu, X; Zang, W
Abstract: Let G be a plane graph, let τ(G) (resp. τ′(G)) be the minimum number of vertices (resp. edges) that meet all cycles of G, and let ν(G) (resp. ν′(G)) be the maximum number of vertex-disjoint (resp. edge-disjoint) cycles in G. In this note we show that τ(G)≤3 ν(G) and τ′(G)≤4 ν′(G)-1; our proofs are constructive, which yield polynomial-time algorithms for finding corresponding objects with the desired properties. © 2011 The Author(s).
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/10722/1471222013-01-01T00:00:00Z
- An efficient algorithm for finding maximum cycle packings in reducible flow graphshttp://hdl.handle.net/10722/48600Title: An efficient algorithm for finding maximum cycle packings in reducible flow graphs
Authors: Chen, X; Zang, W
Abstract: Reducible flow graphs occur naturally in connection with flow-charts of computer programs and are used extensively for code optimization and global data flow analysis. In this paper we present an O(n2m log (n 2/m)) algorithm for finding a maximum cycle packing in any weighted reducible flow graph with n vertices and m arcs. © Springer-Verlag 2004.
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/10722/486002004-01-01T00:00:00Z
- On-line scheduling a batch processing system to minimize total weighted job completion timehttp://hdl.handle.net/10722/75155Title: On-line scheduling a batch processing system to minimize total weighted job completion time
Authors: Chen, B; Deng, X; Zang, W
Abstract: Scheduling a batch processing system has been extensively studied in the last decade.A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch.Th e scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times C j is minimized.In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later.Our objective is to minimize the total weighted completion time σw j C j . We provide a linear time on-line algorithm for the unrestrictive model (i.e., b ≥ n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + ε)-competitive on-line algorithm for any ε > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees. © 2001 Springer Berlin Heidelberg.
Mon, 01 Jan 2001 00:00:00 GMThttp://hdl.handle.net/10722/751552001-01-01T00:00:00Z
- An approximation algorithm for feedback vertex sets in tournamentshttp://hdl.handle.net/10722/42995Title: An approximation algorithm for feedback vertex sets in tournaments
Authors: Cai, MC; Deng, X; Zang, W
Abstract: We obtain a necessary and sufficient condition in terms of forbidden structures for tournaments to possess the min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem in this class of tournaments. Applying the local ratio technique of Bar-Yehuda and Even to the forbidden structures, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.
Mon, 01 Jan 2001 00:00:00 GMThttp://hdl.handle.net/10722/429952001-01-01T00:00:00Z
- Approximating the chromatic index of multigraphshttp://hdl.handle.net/10722/137323Title: Approximating the chromatic index of multigraphs
Authors: Chen, G; Yu, X; Zang, W
Abstract: It is well known that if G is a multigraph then χ′(G) ≥χ′ *(G):=max{Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′ *(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max{2|E(G[U])|/(|U|-1):U ⊇ V(G),|U|≥3,|U| is odd}. The conjecture that χ′(G)≤max{Δ(G)+1,Γ(G) was made independently by Goldberg (Discret. Anal. 23:3-7, 1973), Anderson (Math. Scand. 40:161-175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423-460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′ *(G)+c χ′ *(G) when χ′ *(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋ and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with χ′(G)> ⌊ Δ(G)+ Δ(G)/2 ⌋, improving the above mentioned results. As a consequence, for multigraphs G with χ(G)>Delta(G)+sqrt Δ(G)/2} the answer to a 1964 problem of Vizing is in the affirmative. © 2009 Springer Science+Business Media, LLC.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/10722/1373232011-01-01T00:00:00Z
- Acyclic digraphs with the Gallai-Milgram-Linial property for clique-covershttp://hdl.handle.net/10722/156113Title: Acyclic digraphs with the Gallai-Milgram-Linial property for clique-covers
Authors: Zang, W
Abstract: We present a structural characterization of the class of acyclic digraphs which have the Gallai-Milgram-Linial property for clique-covers. © 1999 Elsevier Science B.V. All rights reserved.
Fri, 01 Jan 1999 00:00:00 GMThttp://hdl.handle.net/10722/1561131999-01-01T00:00:00Z
- An efficient algorithm for finding maximum cycle packings in reducible flow graphshttp://hdl.handle.net/10722/156153Title: An efficient algorithm for finding maximum cycle packings in reducible flow graphs
Authors: Chen, X; Zang, W
Abstract: Reducible flow graphs occur naturally in connection with flowcharts of computer programs and are used extensively for code optimization and global data flow analysis. In this paper we present an O(n2 log(n 2/m)) algorithm for finding a maximum cycle packing in any weighted reducible flow graph with n vertices and m arcs; our algorithm heavily relies on Ramachandran's earlier work concerning reducible flow graphs. © 2005 Springer Science + Business Media, Inc.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/10722/1561532006-01-01T00:00:00Z
- An upper bound for ramsey numbershttp://hdl.handle.net/10722/156178Title: An upper bound for ramsey numbers
Authors: Li, Y; Rousseau, CC; Zang, W
Abstract: Let G″be a graph obtained from G by deleting two vertices. It is shown that r(G, H) ≤A+B+2+2√(A 2+ AB+ B 2)/3, where A = r(G″, H) and B = r(G, H″). © 2004 Elsevier Ltd. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/10722/1561782004-01-01T00:00:00Z
- On-line scheduling a batch processing system to minimize total weighted job completion timehttp://hdl.handle.net/10722/156197Title: On-line scheduling a batch processing system to minimize total weighted job completion time
Authors: Chen, B; Deng, X; Zang, W
Abstract: Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times Cj is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time σ w jCj. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b ≥ n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + 6)-competitive on-line algorithm for any 6 > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/10722/1561972004-01-01T00:00:00Z
- Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphshttp://hdl.handle.net/10722/156154Title: Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
Authors: Zang, W
Abstract: Grillet established conditions on a partially ordered set under which each maximal antichain meets each maximal chain. Berge pointed out that Grillet's theorem can be stated in terms of graphs, made a conjecture that strengthens it, and asked a related question. We exhibit a counterexample to the conjecture and answer the question; then we prove four theorems that generalize Grillet's theorem in the spirit of Berge's proposals. © 1995.
Sun, 01 Jan 1995 00:00:00 GMThttp://hdl.handle.net/10722/1561541995-01-01T00:00:00Z
- Ramsey functions involving Km,n largehttp://hdl.handle.net/10722/156145Title: Ramsey functions involving Km,n large
Authors: Li, Y; Tang, X; Zang, W
Abstract: For fixed integers m,k≥2, it is shown that the k-color Ramsey number rk(Km,n) and the bipartite Ramsey number bk(m,n) are both asymptotically equal to kmn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number r(H+K̄n,Kn) is at most (1+o(1))nm+1/(logn)m-1. Moreover, the order of magnitude of r(H+K̄n,Kn) is proved to be nm+1/(logn)m if H≠Km as n→∞. © 2005 Elsevier B.V. All rights reserved.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10722/1561452005-01-01T00:00:00Z
- Prefacehttp://hdl.handle.net/10722/156237Title: Preface
Authors: Chen, G; Yu, X; Zang, W
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10722/1562372009-01-01T00:00:00Z
- The maximum number of diagonals of a cycle in a block and its extremal graphshttp://hdl.handle.net/10722/156216Title: The maximum number of diagonals of a cycle in a block and its extremal graphs
Authors: Tian, F; Zang, W
Abstract: In this paper we show that if G is a 2-connected graph having minimum degree n such that |V(G)|;≥2n+1, then there exists a cycle in G having more than n(n-2) diagonals, unless G is Kn,m,m>n or the Petersen graph. So the conjecture posed by Gupta, Kahn and Robertson is settled completely. © 1991.
Tue, 01 Jan 1991 00:00:00 GMThttp://hdl.handle.net/10722/1562161991-01-01T00:00:00Z
- Coloring graphs with no odd-K4http://hdl.handle.net/10722/156114Title: Coloring graphs with no odd-K4
Authors: Zang, W
Abstract: The purpose of this note is to present a polynomial-time algorithm which, given an arbitrary graph G as its input, finds either a proper 3-coloring of G or an odd-K4 that is a subgraph of G in time O(mn), where m and n stand for the number of edges and the number of vertices of G, respectively. © 1998 Published by Elsevier Science B.V. All rights reserved.
Thu, 01 Jan 1998 00:00:00 GMThttp://hdl.handle.net/10722/1561141998-01-01T00:00:00Z
- The box-TDI system associated with 2-edge connected spanning subgraphshttp://hdl.handle.net/10722/58970Title: The box-TDI system associated with 2-edge connected spanning subgraphs
Authors: Chen, X; Ding, G; Zang, W
Abstract: Let G be a graph and let A be its cutset-edge incidence matrix. We prove that the linear system frac(1, 2) A x ≥ 1, x ≥ 0 is box totally dual integral (box-TDI) if and only ifG is a series-parallel graph; a by-product of this characterization is a structural description of a box-TDI system on matroids. Our results strengthen two previous theorems obtained respectively by Cornuéjols, Fonlupt, and Naddef and by Mahjoub which assert that both polyhedra {x {divides} frac(1, 2) A x ≥ 1, x ≥ 0} and {x {divides} frac(1, 2) A x ≥ 1, 1 ≥ x ≥ 0} are integral if G is series-parallel. © 2008 Elsevier B.V. All rights reserved.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10722/589702009-01-01T00:00:00Z
- A Unified Approach to Box-Mengerian Hypergraphshttp://hdl.handle.net/10722/207337Title: A Unified Approach to Box-Mengerian Hypergraphs
Authors: Chen, X; Chen, Z; Zang, W
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/10722/2073372010-01-01T00:00:00Z
- Solution to a problem on degree sequences of graphshttp://hdl.handle.net/10722/75478Title: Solution to a problem on degree sequences of graphs
Authors: Cai, MC; Deng, X; Zang, W
Abstract: Let a1,a2,...,an, and b1,b2,...,bn be integers with 0 ≤ ai ≤ bi for i = 1,2,...,n. The purpose of this note is to give a good characterization for the existence of a simple graph G with vertices v1,v2,...,vn such that ai≤dG(vi)≤bi for i = 1,2,...,n. This solves a research problem posed by Niessen and generalizes an Erdos-Gallai theorem. © 2000 Elsevier Science B.V. All rights reserved.
Sat, 01 Jan 2000 00:00:00 GMThttp://hdl.handle.net/10722/754782000-01-01T00:00:00Z
- Packing cycles in graphs, IIhttp://hdl.handle.net/10722/75284Title: Packing cycles in graphs, II
Authors: Ding, G; Xu, Z; Zang, W
Abstract: A graph G packs if for every induced subgraph H of G, the maximum number of vertex-disjoint cycles in H is equal to the minimum number of vertices whose deletion from H results in a forest. The purpose of this paper is to characterize all graphs that pack. © 2002 Elsevier Science (USA). All rights reserved.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/10722/752842003-01-01T00:00:00Z
- A min-max theorem on feedback vertex setshttp://hdl.handle.net/10722/75253Title: A min-max theorem on feedback vertex sets
Authors: Cai, MC; Deng, X; Zang, W
Abstract: We establish a necessary and sufficient condition for the linear system {x : Hx ≥ e, x ≥ 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedbank vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the min-max theorem.
Tue, 01 Jan 2002 00:00:00 GMThttp://hdl.handle.net/10722/752532002-01-01T00:00:00Z
- Continuous optimization and combinatorial optimizationhttp://hdl.handle.net/10722/156248Title: Continuous optimization and combinatorial optimization
Authors: Qi, L; Liao, LZ; Zang, W; Zhou, G
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/10722/1562482010-01-01T00:00:00Z
- Packing cycles in graphshttp://hdl.handle.net/10722/75346Title: Packing cycles in graphs
Authors: Ding, G; Zang, W
Abstract: A graph G is called cycle Mengerian (CM) if for all nonnegative integral function w defined on V(G), the maximum number of cycles (repetition is allowed) in G such that each vertex v is used at most w(v) times is equal to the minimum of ∑ {w(x) : x ∈ X}, where the minimum is taken over all X ⊆ V(G) such that deleting X from G results in a forest. The purpose of this paper is to characterize all CM graphs in terms of forbidden structures. As a corollary, we prove that if the fractional version of the above minimization problem always have an integral optimal solution, then the fractional version of the maximization problem will always have an integral optimal solution as well. 2002 Elsevier Science (USA).
Tue, 01 Jan 2002 00:00:00 GMThttp://hdl.handle.net/10722/753462002-01-01T00:00:00Z
- The lower bound on independence numberhttp://hdl.handle.net/10722/75353Title: The lower bound on independence number
Authors: Li, Y; Rousseau, CC; Zang, W
Abstract: Let G be a graph with degree sequence (d v). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least ∑ vf m+1(d v), where f m+1(x) is a function greater than log(x/(m+1)) - 1/x for x > 0. For a weighted graph G = (V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least ∑ v w v/1 + d v where w v is the weight of v.
Tue, 01 Jan 2002 00:00:00 GMThttp://hdl.handle.net/10722/753532002-01-01T00:00:00Z
- f-Factors in bipartite (mf)-graphshttp://hdl.handle.net/10722/75450Title: f-Factors in bipartite (mf)-graphs
Authors: Liu, G; Zang, W
Abstract: Katerinis and Tsikopoulos (Graphs. Combin. 12 (1996) 327) give sufficient conditions for a regular bipartite graph to have a perfect matching excluding a set of edges. In this paper, we give a necessary and sufficient condition for a bipartite graph to have an f-factor containing a set of edges and excluding another set of edges and discuss some applications of this condition. In particular, we obtain some sufficient conditions related to connectivity and edge-connectivity for a bipartite (mf)-graph to have an f-factor with special properties and generalize the results in (Graphs. Combin. 12 (1996) 327). The results in this paper are in some sense best possible. © 2003 Elsevier B.V. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/10722/754502004-01-01T00:00:00Z
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphshttp://hdl.handle.net/10722/156143Title: A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
Authors: Li, X; Zang, W
Abstract: We present an O(n 5) combinatorial algorithm for the minimum weighted coloring problem on claw-free perfect graphs, which was posed by Hsu and Nemhauser in 1984. Our algorithm heavily relies on the structural descriptions of claw-free perfect graphs given by Chavátal and Sbihi and by Maffray and Reed. © 2005 Springer Science + Business Media, Inc.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10722/1561432005-01-01T00:00:00Z
- Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphshttp://hdl.handle.net/10722/156155Title: Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
Authors: Deng, X; Li, G; Zang, W
Abstract: Grillet established conditions on a partially ordered set under which each maximal antichain meets each maximal chain. Chvátal made a conjecture in terms of graphs that strengthens Grillet's theorem. The purpose of this paper is to prove this conjecture. © 2004 Elsevier Inc. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/10722/1561552004-01-01T00:00:00Z
- Proof of Toft's conjecture: Every graph containing no fully odd K4 is 3-colorablehttp://hdl.handle.net/10722/75159Title: Proof of Toft's conjecture: Every graph containing no fully odd K4 is 3-colorable
Authors: Zang, W
Abstract: A fully odd K4 is a subdivision of K4 such that each of the six edges of the K4 is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K4 can be vertex-colored with three colors. The purpose of this paper is to prove Toft's conjecture. © 1998 Kluwer Academic Publishers.
Thu, 01 Jan 1998 00:00:00 GMThttp://hdl.handle.net/10722/751591998-01-01T00:00:00Z
- A min-max relation on packing feedback vertex setshttp://hdl.handle.net/10722/75457Title: A min-max relation on packing feedback vertex sets
Authors: Chen, X; Ding, G; Hu, X; Zang, W
Abstract: Let G be a graph with a nonnegative integral function w defined on V(G). A family F of subsets of V(G) (repetition is allowed) is called a feedback vertex set packing in G if the removal of any member of F from G leaves a forest, and every vertex v ∈ V(G) is contained in at most w(v) members of F. The weight of a cycle C in G is the sum of w(v), over all vertices v of C. In this paper we characterize all graphs with the property that, for any nonnegative integral function w, the maximum cardinality of a feedback vertex set packing is equal to the minimum weight of a cycle. © Springer-Verlag Berlin Heidelberg 2005.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10722/754572005-01-01T00:00:00Z
- Perfect circular arc coloringhttp://hdl.handle.net/10722/75148Title: Perfect circular arc coloring
Authors: Chen, X; Hu, Z; Zang, W
Abstract: The circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n 2 m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem. © 2005 Springer Science + Business Media, Inc.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10722/751482005-01-01T00:00:00Z
- The complexity of recognizing linear systems with certain integrality propertieshttp://hdl.handle.net/10722/58972Title: The complexity of recognizing linear systems with certain integrality properties
Authors: Ding, G; Feng, L; Zang, W
Abstract: Let A be a 0 - 1 matrix with precisely two 1's in each column and let 1 be the all-one vector. We show that the problems of deciding whether the linear system Ax ≥ 1,x ≥ 0 (1) defines an integral polyhedron, (2) is totally dual integral (TDI), and (3) box-totally dual integral (box-TDI) are all co-NP-complete, thereby confirming the conjecture on NP-hardness of recognizing TDI systems made by Edmonds and Giles in 1984. © 2007 Springer-Verlag.
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/10722/589722008-01-01T00:00:00Z
- Wavelength allocation on trees of ringshttp://hdl.handle.net/10722/156082Title: Wavelength allocation on trees of rings
Authors: Deng, X; Li, G; Zang, W
Abstract: We consider a problem that arises from communication in all-optical networks. Data are transmitted from source nodes to destination nodes via fixed routes. The high bandwidth of the optic fiber allows for wavelength-division multiplexing so that a single physical optical link can carry several logical signals of different wavelengths. The problem is to carry out a set of requests using a limited number of wavelengths so that different routes using the same wavelength never use the same physical link. We focus on trees of rings which are constructed as follows: Start from a tree and replace each node of the tree by a cycle. Each edge in the tree corresponds to the corresponding cycles sharing a common node. We design an approximation algorithm that routes any set of requests on the tree of rings using no more than 2.5wopt wavelengths, where wopt is the minimum possible number of wavelengths for that set of requests. This improves a 3-approximation solution of Raghavan and Upfal. © 2000 John Wiley & Sons, Inc.
Sat, 01 Jan 2000 00:00:00 GMThttp://hdl.handle.net/10722/1560822000-01-01T00:00:00Z
- A Unified Approach to Box-Mengerian Hypergraphshttp://hdl.handle.net/10722/254053Title: A Unified Approach to Box-Mengerian Hypergraphs
Authors: Zang, W
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10722/2540532009-01-01T00:00:00Z
- Packing Circuits in Matroidshttp://hdl.handle.net/10722/254054Title: Packing Circuits in Matroids
Authors: Zang, W; Ding, G
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/10722/2540542008-01-01T00:00:00Z
- The circumference of a graph with no K3,t-minor, IIhttp://hdl.handle.net/10722/164176Title: The circumference of a graph with no K3,t-minor, II
Authors: Chen, G; Yu, X; Zang, W
Abstract: The class of graphs with no K3;t-minors, t>=3, contains all planar graphs and plays an important role in graph minor theory. In 1992, Seymour and Thomas conjectured the existence of a function α(t)>0 and a constant β>0, such that every 3-connected n-vertex graph with no K3;t-minors, t>=3, contains a cycle of length at least α(t)nβ. The purpose of this paper is to con¯rm this conjecture with α(t)=(1/2)t(t-1) and β=log1729 2.
Sun, 01 Jan 2012 00:00:00 GMThttp://hdl.handle.net/10722/1641762012-01-01T00:00:00Z
- Odd-K4's in stability critical graphshttp://hdl.handle.net/10722/156243Title: Odd-K4's in stability critical graphs
Authors: Chen, Z; Zang, W
Abstract: A subdivision of K4 is called an odd-K4 if each triangle of the K4 is subdivided to form an odd cycle, and is called a fully odd-K4 if each of the six edges of the K4 is subdivided into a path of odd length. A graph G is called stability critical if the deletion of any edge from G increases the stability number. In 1993, Sewell and Trotter conjectured that in a stability critical graph every triple of edges which share a common end is contained in a fully odd-K4. The purpose of this note is to show that such a triple is contained in an odd-K4. © 2009 Elsevier B.V. All rights reserved.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10722/1562432009-01-01T00:00:00Z
- Nowhere-zero 4-flows, simultaneous edge-colorings, and critical partial latin squareshttp://hdl.handle.net/10722/75282Title: Nowhere-zero 4-flows, simultaneous edge-colorings, and critical partial latin squares
Authors: Luo, R; Zang, W; Zhang, CQ
Abstract: It is proved in this paper that every bipartite graphic sequence with the minimum degree δ ≥ 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell (1993) and reproposed by Cameron (1999) about simultaneous edge-colorings and critical partial Latin squares. © 2004 János Bolyai Mathematical Society.
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/10722/752822004-01-01T00:00:00Z
- A 2-approximation algorithm for path coloring on a restricted class of trees of ringshttp://hdl.handle.net/10722/75160Title: A 2-approximation algorithm for path coloring on a restricted class of trees of rings
Authors: Deng, X; Li, G; Zang, W; Zhou, Y
Abstract: A tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle (called tree-node-cycle) and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common and no three tree-node-cycles share a same node. (A more general definition may allow them to share the same node.) Given a set of paths on a tree of rings, the path coloring problem is to color these paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. In this paper, we present a 2-approximation algorithm for this problem.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/10722/751602003-01-01T00:00:00Z
- Bonds with parity constraintshttp://hdl.handle.net/10722/137324Title: Bonds with parity constraints
Authors: Chen, X; Ding, G; Yu, X; Zang, W
Abstract: Given a connected graph G=(V, E) and three even-sized subsets A 1, A 2, A 3 of V, when does V have a partition (S 1, S 2) such that G[S i] is connected and |S i∩A j| is odd for all i=1, 2 and j=1, 2, 3? This problem arises in the area of integer flow theory and has theoretical interest in its own right. The special case when |A 1|=|A 2|=|A 3|=2 has been resolved by Chakravarti and Robertson, and the general problem can be rephrased as a problem on binary matroids that asks if a given triple of elements is contained in a circuit. The purpose of this paper is to present a complete solution to this problem based on a strengthening of Seymour's theorem on triples in matroid circuits. © 2011 Elsevier Inc.
Sun, 01 Jan 2012 00:00:00 GMThttp://hdl.handle.net/10722/1373242012-01-01T00:00:00Z
- A unified approach to box-mengerian hypergraphshttp://hdl.handle.net/10722/124810Title: A unified approach to box-mengerian hypergraphs
Authors: Chen, X; Chen, Z; Zang, W
Abstract: A hypergraph is called box-Mengerian if the linear system Ax ≥ 1, x ≥ 0 is box-totally dual integral (box-TDI), where A is the edge-vertex incidence matrix of the hypergraph. Because it is NP-hard in general to recognize box-Mengerian hypergraphs, a basic theme in combinatorial optimization is to identify such objects associated with various problems. In this paper, we show that the so-called equitably subpartitionable (ESP) property, first introduced by Ding and Zang (Ding, G., W. Zang. 2002. Packing cycles in graphs. J. Combin. Theory Ser. B 86 381-407) in their characterization of all graphs with the min-max relation on packing and covering cycles, turns out to be even sufficient for box-Mengerian hypergraphs. We also establish several new classes of box-Mengerian hypergraphs based on ESP property. This approach is of transparent combinatorial nature and is hence fairly easy to work with. Copyright © 2010 INFORMS.
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/10722/1248102010-01-01T00:00:00Z