Menu
Home
Contact us
Stats
Categories
Calendar
Toggle Wiki
Wiki Home
Last Changes
Rankings
List pages
Orphan pages
Sandbox
Print
Toggle Image Galleries
Galleries
Rankings
Toggle Articles
Articles home
List articles
Rankings
Toggle Blogs
List blogs
Rankings
Toggle Forums
List forums
Rankings
Toggle File Galleries
List galleries
Rankings
Toggle Maps
Mapfiles
Toggle Surveys
List surveys
Stats
ITHEA Classification Structure > G. Mathematics of Computing  > G.2 DISCRETE MATHEMATICS  > G.2.1 Combinatorics 
ON THE STRUCTURE OF MAXIMUM INDEPENDENT SETS IN BIPARTITE GRAPHS
By: Vahagn Minasyan (2296 reads)
Rating: (1.00/10)

Abstract: In this paper it is shown that for bipartite graphs the structure of the family of maximum independent sets can be described constructively, in the following sense. For a bipartite graph there are some “basic” maximum independent sets, in terms of which any maximum independent set can be described, in the sense that there is one-to-one correspondence between a maximum independent set and an irreducible combination of these “basic” maximum independent sets. König’s theorem states that there is duality between the cardinalities of maximum matching and minimum vertex cover. Viewing the mentioned structure, in this paper it is shown that another duality holds, which is between the sets rather than their cardinalities. We believe that this duality is not just of theoretical interest, but it also can yield to a usable algorithm for finding a maximum matching of bipartite graph. In this paper we do not present such algorithm; instead we mention what approaches we plan to use in further works to obtain such algorithm.

Keywords: bipartite graph, maximum independent set, distributive lattice, duality.

ACM Classification Keywords:G.2.1 Discrete mathematics: Combinatorics

Link:

ON THE STRUCTURE OF MAXIMUM INDEPENDENT SETS IN BIPARTITE GRAPHS

Vahagn Minasyan

http://www.foibg.com/ijita/vol17/ijita17-2-p06.pdf

Print
G.2.1 Combinatorics
article: RANDOMIZED SET SYSTEMS CONSTRAINED BY THE DISCRETE TOMOGRAPHY · A NEW ALGORITM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM · ON THE STRUCTURE OF MAXIMUM INDEPENDENT SETS IN BIPARTITE GRAPHS · SOME PROPERTIES IN MULTIDIMENSIONAL MULTIVALUED DISCRETE TORUS · ON PROBLEM OF ADEQUACY OF MULTISET MATHEMATICAL MODELS · SPREADING THE MOORE - PENROSE PSEUDO INVERSE ON MATRICES EUCLIDEAN SPACES: ... · VECTORS AND MATRIXES IN GROUPING INFORMATION PROBLEM · CHOICE OF DIAGNOSTIC DECISION MAKING IN MEDICINE AND INTERVENTION MISTAKE ... · RECURRENT PROCEDURE IN SOLVING THE GROUPING INFORMATION PROBLEM IN APPLIED... · ‘FEATURE VECTORS’ IN GROUPING INFORMATION PROBLEM IN APPLIED MATHEMATICS: .. · DECOMPOSITION METHODS FOR LARGE-SCALE TSP · ON THE DISCRETIZATION OF DISTANCE GEOMETRY PROBLEMS · REGULAR INVERSIVE POLYTOPES · LOGARITHMIC DISTANCES IN GRAPHS · FUZZY SETS AS A MEAN FOR UNCERTAINTY HANDLING: MATH, APPLIED MATH, HEURISTICS · FUZZY SETS: MATH, APPLIED MATH, HEURISTICS? PROBLEMS AND INTERPRETATIONS · CROSS INTERSECTION SEQUEL OF DISCRETE ISOPERIMETRY1 · GENERATING MORE BOUNDARY ELEMENTS OF SUBSET PROJECTIONS · MULTICRITERION PROBLEMS ON THE COMBINATORIAL SET OF POLYARRANGEMENTS · CHAIN SPLIT OF PARTIALLY ORDERED SET OF K-SUBSETS · SOLVING LARGE SYSTEMS OF BOOLEAN EQUATIONS · LAGRANGEAN APPROXIMATION FOR COMBINATORIAL INVERSE PROBLEMS · MULTICRITERION PROBLEMS ON THE COMBINATORIAL SET OF POLYARRANGEMENTS · DESCRIPTION REDUCTION FOR RESTRICTED SETS OF (0,1) MATRICES 1 · DECOMPOSITION OF BOOLEAN FUNCTIONS – RECOGNIZING A GOOD SOLUTION BY TRACES · THE BOUNDARY DESCRIPTORS OF THE n-DIMENSIONAL UNIT CUBE SUBSET PARTITIONING1 · RANDOMIZED PARALLELIZATION – A NEW METHOD FOR SOLVING ... · OPTIMIZATION OF ATM TELECOMMUNICATION NETWORKS · VECTOR COMBINATORIAL PROBLEMS IN A SPACE OF COMBINATIONS ... ·
Login
[ register | I forgot my password ]
World Clock
Powered by Tikiwiki Powered by PHP Powered by Smarty Powered by ADOdb Made with CSS Powered by RDF powered by The PHP Layers Menu System
RSS Wiki RSS Blogs rss Articles RSS Image Galleries RSS File Galleries RSS Forums RSS Maps rss Calendars
[ Execution time: 0.08 secs ]   [ Memory usage: 7.57MB ]   [ GZIP Disabled ]   [ Server load: 0.13 ]
Powered by Tikiwiki CMS/Groupware