Efficient algorithms for graphs with few \(P_4\)'s (Q5937917): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Add wikidata item.
 
(3 intermediate revisions by 3 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(00)00258-2 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2062287043 / rank
 
Normal rank
Property / Wikidata QID
 
Property / Wikidata QID: Q128109451 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

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