Keyword: NP-complete

Found 15 papers in total
On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
2017,
Fan‐planar graphs were recently introduced as a generalization of 1‐...
Public facility location using dispersion, population, and equity criteria
Public facility location using dispersion, population, and equity criteria
2014,
From a practical perspective, the paper demonstrates that the appropriate use of...
Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction
Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction
2013,
The compaction problem is to partition the vertices of an input graph G onto the...
Satisfiability problem for modal logic with global counting operators coded in binary is NExpTime-complete
Satisfiability problem for modal logic with global counting operators coded in binary is NExpTime-complete
2013,
This paper provides a proof of NExpTime ‐completeness of the satisfiability...
Complexity of Finding Graph Roots with Girth Conditions
Complexity of Finding Graph Roots with Girth Conditions
2012,
Graph G is the square of graph H if two vertices x , y have an edge in G if and only...
The k‐in‐a‐Path Problem for Claw‐free Graphs
The k‐in‐a‐Path Problem for Claw‐free Graphs
2012,
The k ‐ in‐a‐Path problem is to test whether a graph contains an...
Finding Induced Paths of Given Parity in Claw‐Free Graphs
Finding Induced Paths of Given Parity in Claw‐Free Graphs
2012,
The Parity Path problem is to decide if a given graph contains both an induced path of...
Uniquely Restricted Matchings
Uniquely Restricted Matchings
2001,
A matching in a graph is a set of edges no two of which share a common vertex. In this...
The Complexity of König Subgraph Problems and Above‐Guarantee Vertex Cover
The Complexity of König Subgraph Problems and Above‐Guarantee Vertex Cover
2011,
A graph is König‐Egerváry if the size of a minimum vertex cover...
Minimizing the sum cost in linear extensions of a poset
Minimizing the sum cost in linear extensions of a poset
2011,
A linear extension problem is defined as follows: Given a poset P =( E ,≤), we want...
Crossing Numbers of Graphs with Rotation Systems
Crossing Numbers of Graphs with Rotation Systems
2011,
We show that computing the crossing number and the odd crossing number of a graph with...
Minimum cost flows with minimum quantities
Minimum cost flows with minimum quantities
2011,
? Proof of strong NP‐completeness of Min Cost Network Flow with Minimum...
Charge and reduce: A fixed‐parameter algorithm for String‐to‐String Correction
Charge and reduce: A fixed‐parameter algorithm for String‐to‐String Correction
2011,
String distance problems typically ask for a minimum number of permitted operations to...
The complexity of domination problems in circle graphs
The complexity of domination problems in circle graphs
1993,
Circle graphs are the intersection graphs of chords of a circle. This paper shows that...
Local search and the local structure of NP-complete problems
Local search and the local structure of NP-complete problems
1992,
It is shown that certain NP-complete problems (traveling salesman, min-cut graph...
Papers per page: