NDLI: The Linkage of a Graph

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

The Linkage of a Graph

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Thilikos, Dimitris M. Kirousis, Lefteris M.
Copyright Year	1996
Abstract	The linkage of a graph is defined to be the maximum mm-degree of any of its subgraphs It is known that the linkage of a graph is equal to its width: for an arbitrary linear ordering of the vertices of the graph, consider the maximum, with respect to any vertex v, of the number of vertices connected with v and preceding it in the ordering; the width of the graph is the minimum of these maxima over all possible linear orderings. Width has been used in artificial intelligence in the context of constraint satisfaction problems (CSPs). A more general notion is defined by considering not the number of vertices preceding and connected with v but rather the least number of vertices preceding and connected with any cluster of at most j consecutive vertices extending to the right up to v (j is a given integer). The graph parameter thus defined is called j-width. No efficient algorithm was known for computing the j-width. In this paper, we introduce a graph parameter depending on j that refers to the subgraphs of the graph and generalizes the notion of linkage. We prove the minmax theorem that this graph parameter, which we call j-linkage, is equal to j-width, and we then give a polynomial-time algorithm for computing it (for constant j). We also find tight lower and upper bounds for the j-linkage (equivalently, the j-width) of graphs with given numbers of vertices and edges. It is interesting to note that a lower bound for the width of a graph had been found by Erds; as we show, however, that bound is not tight. Moreover, we prove that our lower bound for width is also a tight lower bound for treewidth, pathwidth, and bandwidth, graph parameters that may be arbitrarily larger than width. Finally, we show that computing the j-linkage is a P-complete problem, whereas we prove that approximating it is a threshold problem: it is in NC for approximation factors $ < {1 / {(2j)}}$, and it is P-complete for approximation factors $ > {1 / 2}$.
Starting Page	626
Ending Page	647
Page Count	22
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539793255709
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	25
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-13
Access Restriction	Subscribed
Subject Keyword	linkage of a graph Analysis of algorithms and problem complexity algorithms in NC P-complete problems extremal graph properties Graph theory Extremal problems width parameters of a graph Graph algorithms backtrack-free search Complexity classes
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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

Parallel Complexity of the Connected Subgraph Problem

The Complexity of Modular Graph Automorphism

The Complexity of Planar Counting Problems

Simple Local Search Problems that are Hard to Solve

On Conflict-Free Cuts: Algorithms and Complexity

Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory

Candy-passing Games on General Graphs, II

Fractals for Kernelization Lower Bounds

Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques

The Linkage of a Graph

Similar Documents

Parallel Complexity of the Connected Subgraph Problem

The Complexity of Modular Graph Automorphism

The Complexity of Planar Counting Problems

Simple Local Search Problems that are Hard to Solve

On Conflict-Free Cuts: Algorithms and Complexity

Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory

Candy-passing Games on General Graphs, II

Fractals for Kernelization Lower Bounds

Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques

The Linkage of a Graph