Combinatorial and Graph-Theoretical Problems and Augmenting Technique

Ngoc C. Lê
Additional contact information
Ngoc C. Lê: Hanoi University of Science and Technology

A chapter in Optimization Problems in Graph Theory, 2018, pp 169-213 from Springer

Abstract: Abstract The notion of augmenting graphs generalizes Berge’s idea of augmenting chains, which was used by Edmonds in his celebrated so-called Blossom Algorithm for the maximum matching problem (Edmonds, Can J Math 17:449–467, 1965). This method then was developed for more general maximum independent set (MIS) problem, first for claw-free graphs (Minty, J Comb Theory Ser B 28(3):284–304, 1980; Sbihi, Discret Math 29(1):53–76, 1980). Then the method was used extensively for various special cases, for example, S 1,1,2 (or fork)-free graphs (Alekseev, Discret Anal Oper Res Ser 1:3–19, 1999), subclasses of P 5 free graphs (Boliac and Lozin, Discret Appl Math 131(3):567–575, 2003; Gerber et al., Discret Appl Math 132(1–3):109–119, 2004; Mosca, Discret Appl Math 132(1–3):175–183, 2004; Lozin and Mosca, Inf Process Lett 109(6):319–324, 2009), P 6-free graphs (Mosca, Discuss Math Graph Theory 32(3):387–401, 2012), S 1,2,l-free graphs (Hertz et al., Inf Process Lett 86(3):311–316, 2003; Hertz and Lozin, The maximum independent set problem and augmenting graphs. In: Graph theory and combinatorial optimization. Springer Science and Business Media, New York, pp. 69–99, 2005), S 1,2,5-free graphs (Lozin and Milanič, Discret Appl Math 156(13):2517–2529, 2008), and for S 1,1,3-free graphs (Dabrowski et al., Graphs Comb 32(4):1339–1352, 2016). In this paper, we will extend the method for some more general graph classes. Our objective is combining these approaches to apply this technique to develop polynomial time algorithms for the MIS problem in some special subclasses of S 2,2,5-free graphs, extending in this way different known results. Moreover, we also consider the augmenting technique for some other combinatorial graph-theoretical problems, for example maximum induced matching, maximum multi-partite induced subgraphs, maximum dissociative set, etc.

Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-94830-0_9

Ordering information: This item can be ordered from
http://www.springer.com/9783319948300

DOI: 10.1007/978-3-319-94830-0_9

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().