HOPS web view

This page lists:


Parameters

This browser does not support PDFs. Please download the PDF to view it: Download PDF.


All parameters in HOPS

ParameterRelevance
acyclic chromatic number█████░░░░
arboricity█████░░░░
average degree██░░░░░░░
average distance███░░░░░░
bandwidth█████░░░░
bipartite number██░░░░░░░
bisection bandwidth████░░░░░
book thickness████░░░░░
boolean width█████░░░░
bounded components███░░░░░░
boxicity██████░░░
branch width█████░░░░
c-closure░░░░░░░░░
carving-width███░░░░░░
chordality████░░░░░
chromatic number█████░░░░
clique cover number█████░░░░
clique-tree-width██░░░░░░░
clique-width███████░░
cutwidth████░░░░░
d-path-free██░░░░░░░
degeneracy██████░░░
degree treewidth██████░░░
diameter██████░░░
diameter+max degree█████░░░░
distance to bipartite██████░░░
distance to block████░░░░░
distance to bounded components████░░░░░
distance to chordal████░░░░░
distance to cluster█████░░░░
distance to co-cluster█████░░░░
distance to cograph█████░░░░
distance to complete██████░░░
distance to edgeless█░░░░░░░░
distance to forest█████░░░░
distance to interval███░░░░░░
distance to linear forest████░░░░░
distance to maximum degree████░░░░░
distance to outerplanar███░░░░░░
distance to perfect████░░░░░
distance to planar████░░░░░
distance to stars███░░░░░░
domatic number███░░░░░░
domination number███░░░░░░
edge clique cover number████░░░░░
edge connectivity██░░░░░░░
feedback edge set██████░░░
feedback vertex set████████░
genus██░░░░░░░
girth█░░░░░░░░
h-index████░░░░░
inf-flip-width███░░░░░░
iterated type partitions███░░░░░░
linear clique-width█████░░░░
linear NLC-width██░░░░░░░
linear rank-width██░░░░░░░
maximum clique█████░░░░
maximum degree████████░
maximum independent set██░░░░░░░
maximum induced matching███░░░░░░
maximum leaf number██████░░░
maximum matching███░░░░░░
maximum matching on bipartite graphs░░░░░░░░░
mim-width██████░░░
minimum degree░░░░░░░░░
mm-width████░░░░░
modular-width███████░░
module-width██████░░░
neighborhood diversity██████░░░
NLC-width████░░░░░
NLCT-width██░░░░░░░
odd cycle transversal██████░░░
pathwidth████████░
pathwidth+maxdegree███░░░░░░
radius-r flip-width███░░░░░░
rank-width███████░░
shrub-depth██████░░░
sim-width█████░░░░
topological bandwidth████░░░░░
tree-independence number█████░░░░
treedepth███████░░
treelength██████░░░
treewidth█████████
twin-cover number█████░░░░
twin-width████████░
vertex connectivity░░░░░░░░░
vertex cover█████████
vertex integrity██████░░░

Graph classes

Some parameters are derived from associated graph classes. Graph classes can be also used as witnesses of proper inclusions. For these purposes, we use the following graph class hierarchy. We assume that all of the graph class inclusions are proper.

We aim to have here only the graph classes that influence parameter inclusions. Please, see Information System on Graph Classes and their Inclusions (ISGCI) for an exhaustive list of graph classes and their inclusions.

Graph hierarchy DOT

Graph classRelevance
bipartite████████░
block████░░░░░
chordal█████░░░░
cluster██████░░░
co-cluster██████░░░
cograph███████░░
complete█████████
connected██░░░░░░░
cycle██░░░░░░░
cycles████░░░░░
disjoint cycles████░░░░░
edgeless█░░░░░░░░
forest█████████
grid██████░░░
interval███████░░
linear forest████░░░░░
outerplanar█████░░░░
path███░░░░░░
perfect██████░░░
planar████████░
star███░░░░░░
stars████░░░░░
tree███████░░

Sources

OrderYearSource
0002024Parameterized complexity for iterated type partitions and modular-width by Cordasco, Gargano, Rescigno
0012024Twin-width of graphs on surfaces by Kráľ, Pekárková, Štorgel
0022023On Algorithmic Applications of Sim-Width and Mim-Width of $(H_1,H_2)$-Free Graphs by Munaro, Yang
0032023Flip-width: Cops and Robber on dense graphs by Toruńczyk
0042022Expanding the Graph Parameter Hierarchy by Tran
0052021Twin-width I: Tractable FO Model Checking by Bonnet, Kim, Thomassé, Watrigant
006unknownComparing Graph Parameters by Schröder
0072020Mim-Width I. Induced path problems by Jaffke, Kwon, Telle
0082019The Graph Parameter Hierarchy by Sorge
0092019Shrub-depth: Capturing Height of Dense Graphs by Ganian, Hliněný, Nešetřil, Obdržálek, Mendez
0102018A systematic comparison of graph parameters by Frömmrich
0112017Graph Theory by Diestel
0122015Parameterized Algorithms by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh
0132015Improving Vertex Cover as a Graph Parameter by Ganian
0142015Linear rank-width and linear clique-width of trees by Adler, Kanté
0152013The Power of Data Reduction: Kernels for Fundamental Graph Problems by Jansen
0162013Characterizing graphs of small carving-width by Belmonte, van ’t Hof, Kamiński, Paulusma, Thilikos
0172013Parameterized Algorithms for Modular-Width by Gajarský, Lampis, Ordyniak
0182012New Width Parameters of Graphs by Vatshelle
0192012Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
0202012Algorithmic Meta-theorems for Restrictions of Treewidth by Lampis
0212011Boolean-width of graphs by Bui-Xuan, Telle, Vatshelle
0222011Chordal Bipartite Graphs with High Boxicity by Chandran, Francis, Mathew
0232010Comparing 17 graph parameters by Sasák
0242010The rank-width of the square grid by Jelínek
0252009Clique-Width is NP-Complete by Fellows, Rosamond, Rotics, Szeider
0262008Grad and classes with bounded expansion II. Algorithmic aspects by Nešetřil, Ossona de Mendez
0272008Spanning Trees with Many Leaves and Average Distance by DeLaViña, Waller
0282007Graph Treewidth and Geometric Thickness Parameters by Dujmovic, Wood
0292006Approximating clique-width and branch-width by Oum, Seymour
0302005On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
0312004Track Layouts of Graphs by Dujmović, Pór, Wood
0322000Upper bounds to the clique width of graphs by Courcelle, Olariu
0331998Clique-decomposition, NLC-decomposition and modular decomposition—relationships and results for random graphs by Johansson
0341998A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
0351994k-NLC graphs and polynomial algorithms by Wanke
0361993The Pathwidth and Treewidth of Cographs by Bodlaender, Möhring
0371991Graph minors. X. Obstructions to tree-decomposition by Robertson, Seymour
0381986Graph minors. V. Excluding a planar graph by Robertson, Seymour
0391994Genus g Graphs Have Pagenumber O(√g) by Malitz
0401993On the chordality of a graph by McKee, Scheinerman
0411986Graph minors. II. Algorithmic aspects of tree-width by Robertson, Seymour
0421988The average distanceisnot morethan the independence number by Chung
0431985On the Cutwidth and the Topological Bandwidth of a Tree by Chung

Tags