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
    0 references
    0 references
    0 references
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references