NDLI: Local Structure When All Maximal Independent Sets Have Equal Weight

Please wait, while we are loading the content...

Local Structure When All Maximal Independent Sets Have Equal Weight

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Caro, Yair Ramey, J. E. Ellingham, M. N.
Copyright Year	1998
Abstract	In many combinatorial situations there is a notion of independence of a set of points. Maximal independent sets can be easily constructed by a greedy algorithm, and it is of interest to determine, for example, if they all have the same size or the same parity. Both of these questions may be formulated by weighting the points with elements of an abelian group, and asking whether all maximal independent sets have equal weight. If a set is independent precisely when its elements are pairwise independent, a graph can be used as a model. The question then becomes whether a graph, with its vertices weighted by elements of an abelian group, is well-covered, i.e., has all maximal independent sets of vertices with equal weight. This problem is known to be co-NP-complete in general. We show that whether a graph is well-covered or not depends on its local structure. Based on this, we develop an algorithm to recognize well-covered graphs. For graphs with n vertices and maximum degree $\Delta$, it runs in linear time if $\Delta$ is bounded by a constant, and in polynomial time if $\Delta = O(\root 3 \of {\log n})$. We mention various applications to areas including hypergraph matchings and radius k independent sets. We extend our results to the problem of determining whether a graph has a weighting which makes it well-covered.
Starting Page	644
Ending Page	654
Page Count	11
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480196300479
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	11
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-01
Access Restriction	Subscribed
Subject Keyword	independence system recognition algorithm Factorization, matching, partitioning, covering and packing local structure Matroids, geometric lattices maximal independent set Structural characterization of families of graphs well-covered graph Graph theory Graph algorithms hypergraph matching polynomial time algorithm
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On Maximal Independent Arborescence Packing

Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered Graphs

Matroids Induced by Packing Subgraphs

Covering Intersecting Bi-set Families under Matroid Constraints

Packing of maximal independent mixed arborescences

The Independent Even Factor Problem

Making Bipartite Graphs DM-Irreducible

Packing $k$-Matchings and $k$-Critical Graphs

Choice Functions

Local Structure When All Maximal Independent Sets Have Equal Weight

Similar Documents

On Maximal Independent Arborescence Packing

Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered Graphs

Matroids Induced by Packing Subgraphs

Covering Intersecting Bi-set Families under Matroid Constraints

Packing of maximal independent mixed arborescences

The Independent Even Factor Problem

Making Bipartite Graphs DM-Irreducible

Packing $k$-Matchings and $k$-Critical Graphs

Choice Functions

Local Structure When All Maximal Independent Sets Have Equal Weight