Efficient algorithms for graphs with few \(P_4\)'s (Q5937917): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Add wikidata item. |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q128109451 / rank | |||
Normal rank |
Latest revision as of 08:39, 12 December 2024
scientific article; zbMATH DE number 1621226
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient algorithms for graphs with few \(P_4\)'s |
scientific article; zbMATH DE number 1621226 |
Statements
Efficient algorithms for graphs with few \(P_4\)'s (English)
0 references
18 July 2001
0 references
A graph is called \((q,t)\)-graph if no set of at most \(q\) vertices induces more than \(t\) distinct \(P_4\)'s. The authors show that many NP-complete problems can be solved efficiently for graphs with ``few'' \(P_4\)'s. They consider domination problems (domination, total domination, independent domination, connected domination and dominating clique), the Steiner tree problem, the vertex ranking problem, the pathwidth problem, the path cover number problem, the Hamiltonian circuit problem, the list coloring problem and the precoloring extension problem. They show that all these problems can be solved in linear time for the class of \((q,q-4)\)-graphs.
0 references
NP-complete problems
0 references
domination
0 references
Steiner tree problem
0 references
vertex ranking
0 references
pathwidth
0 references
Hamiltonian circuit problem
0 references
coloring
0 references