NDLI: Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Berry, A. Krueger, R. Simonet, G.
Copyright Year	2009
Abstract	Many graph search algorithms use a vertex labeling to compute an ordering of the vertices. We examine such algorithms which compute a peo (perfect elimination ordering) of a chordal graph and corresponding algorithms which compute an meo (minimal elimination ordering) of a non-chordal graph, an ordering used to compute a minimal triangulation of the input graph. We express all known peo-computing search algorithms as instances of a generic algorithm called MLS (maximal label search) and generalize Algorithm MLS into CompMLS, which can compute any peo. We then extend these algorithms to versions which compute an meo and likewise generalize all known meo-computing search algorithms. We show that not all minimal triangulations can be computed by such a graph search, and, more surprisingly, that all these search algorithms compute the same set of minimal triangulations, even though the computed meos are different. Finally, we present a complexity analysis of these algorithms. An extended abstract of part of this paper was published in WG 2005 .
Starting Page	428
Ending Page	446
Page Count	19
File Format	PDF
ISSN	08954801
DOI	10.1137/070684355
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	23
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-01-16
Access Restriction	Subscribed
Subject Keyword	elimination scheme meo graph search peo Graph algorithms maximal label search minimal triangulation
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

Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings

Maximal label search algorithms to compute perfect and minimal elimination orderings

Maximal label search algorithms to compute perfect and minimal elimination orderings (2009)

Moplex Elimination Orderings (2001)

Computing a Clique Tree with the Algorithm Maximal Label Search

Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs

A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph

Exact Algorithms for Treewidth and Minimum Fill-In

On Distance-Preserving and Domination Elimination Orderings

Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings

Similar Documents

Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings

Maximal label search algorithms to compute perfect and minimal elimination orderings

Maximal label search algorithms to compute perfect and minimal elimination orderings (2009)

Moplex Elimination Orderings (2001)

Computing a Clique Tree with the Algorithm Maximal Label Search

Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs

A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph

Exact Algorithms for Treewidth and Minimum Fill-In

On Distance-Preserving and Domination Elimination Orderings

Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings